条件最短路径type
status
date
slug
summary
tags
category
icon
password
Property
最短路径问题是图论中求两个顶点之间的最短路径问题，通常是求最短加权路径。
条件最短路径，指带有约束条件、限制条件的最短路径。例如，顶点约束，包括必经点或禁止点的限制；边的约束，包括必经路段或禁止路段；还包括无权路径长度的限制，即经过几步到达终点。进一步地，还有双目标限制的最短路径问题，求最短距离中花费最小的路线；交通限制条件下的最短路径问题，需要考虑转向限制和延误的约束。
求解带有限制条件的最短路径问题，总体可以分为两类基本方法：一类是基于不带限制条件的最短路径算法，对求解过程中的每一条有效路径，都用限制条件进行判断，如果满足所有限制条件则继续，如果不满足限制条件则放弃该路径；另一类方法是基于具体问题和选择算法的特点，将问题转化为有约束的规划问题来处理。
但是，如果使用 NetworkX 求解带有限制条件的最短路径问题，采用这两类方法都会有一些困难。原因在于NetworkX 提供的 Dijkstra 算法、Bellman-Ford 算法、Floyd 算法和启发式算法 A* 都是封装函数，没有提供设置约束条件的选项和接口，因此用户不能把条件判断语句加入这些封装函数的程序内部。
不过，NetworkX 可以生成两个顶点之间的所有简单路径，而且可以获得所有简单路径的边的列表。利用简单路径算法，可以通过对约束条件的判断来求解带有顶点约束和边约束的最短路径问题。
问题案例：蚂蚁的最优路径分析
蚁巢有若干个储藏间（图中圆圈表示），储藏间之间有路径相连（路径拓扑结构如图所示）。该图为无向图，路径通行的花费如图中线路上的数字所示，路径正反方向通行的花费相同。要求从起点 N0 到终点 N17 的最优路径，并需要满足限制条件：
- 需要尽可能以最少的花费到达终点；
- 必须经过图中的绿色节点；
- 必须经过图中的两段绿色路段；
- 必须避开图中的红色路段。
图的创建和可视化
运行结果
本段程序绘制网络图，包括顶点、边、边的权值，特殊顶点和特殊边的颜色设置
- 图的创建。本例使用
nx.Graph()创建无向图，然后用gAnt.add_weighted_edges_from()函数以列表向图中添加多条赋权边，每个赋权边以元组 (node1,node2,weight) 表示
- 图的绘制。使用
nx.draw()绘图时，默认的节点位置并不理想，可以使用 pos 属性参数指定节点位置。pos 为字典数据类型，按 node:(x_pos,y_pos) 格式设置节点位置。
- 显示边的权值。使用
nx.draw_networkx_edge_labels()可以绘制边的属性，本例中选择显示权值属性。
- 设置顶点属性。
nx.draw_networkx_nodes()可以设置顶点的属性，例如对 nodelist 列表中的节点设置颜色属性 node_color。
- 设置边的属性。
nx.draw_networkx_edges()可以设置边的属性，例如对 edgelist 列表中的边设置线宽属性 width 和颜色属性 edge_color。
无限制条件的最短路径
- 对于无限制条件的最短路径问题，NetworkX 提供了 Dijkstra 算法、Bellman-Ford 算法、Floyd 算法和启发式算法 A* 的函数。
- 例程使用 nx.dijkstra_path() 和 nx.dijkstra_path_length() 调用 Dijkstra 算法求两个指定顶点之间的最短加权路径和最短加权路径长度。
限制条件：禁止点或禁止边
- 禁止点或者禁止边的处理比较简单，从图中删除对应的禁止顶点或禁止边即可。当然，在创建图时就不添加这些顶点和边更简单，但这样在绘图时也无法反映这些顶点和边。
- 使用
remove_node(n)删除指定顶点 n，remove_edge(u,v)删除指定的边 (u,v)。
- 使用
remove_nodes_from([n1,…nk])删除多个顶点，remove_edges_from([(u1,v1),…(uk,vk)])删除多条边。
- 例程中删除的点和边与案例问题中的要求不一致，是为了示例删除函数的使用。
限制条件：一个必经点
- 当限制条件为一个必经点时，可以把原问题分解为两个子问题：子问题 1 为起点至必经点，子问题 2 为必经点至终点。
- 对两个子问题分别用 Dijkstra 算法求最短加权路径和最短加权路径长度，然后进行合并，就得到经过必经点的原问题的最短加权路径和最短加权路径长度。
限制条件：多个必经点（方案一）
- 当限制条件为两个或多个必经点时，起点、终点与各必经点的次序并不确定，即从起点出发就不知道应该先去哪一个必经点，因此不宜再用分段求最小路径的方法处理。
- NetworkX 提供了 all_simple_paths() 函数，可以生成两个顶点之间的所有简单路径。利用简单路径算法，可以通过对约束条件的判断来求解带有多个顶点约束的最短路径问题。
- 程序实现的步骤包括：（1）遍历起点为0、终点为17的简单路径；（2）检查路径是否满足包括顶点 N7、N15 的限制条件；（3）在满足限制条件的简单路径中找加权长度最短的路径；（4）求最短路径的加权路径长度。
- 本段例程非常简练，综合使用了几种 Python 语言循环、判断结构的简洁写法，需要逐步分析。
限制条件：多个必经点（方案二）
- 本例与 3.5 的问题实际上是相同的。限制条件都是多个必经顶点 N7、N15，解决方案都是使用 all_simple_paths() 函数生成两个顶点间的所有简单路径，程序实现的步骤也是类似的。
- 本方案按照典型的循环、判断结构的写法，便于阅读和理解。此外，如果还有其它约束条件或子任务需要在循环中处理，这样的结构更容易实现。
Python 例程
限制条件：必经边
- 必经点的处理，实际上还可以有更好的方法，其思想是结合 Dijkstra 算法的实现过程， 将限制条件作为缩小搜索空间的条件，可以降低算法的复杂度。但对于多个必经边来说，很难以此来改进基础的无约束算法，通常的处理方法就是在算法中增加一个判断是否满足约束条件的过程。
- 本例仍然延续处理多个必经点的思路，利用简单路径算法，可以通过对约束条件的判断来求解带有多个必经边约束条件的最短路径问题，可以同时处理必经点约束条件。
- 本例程对应案例中的各项约束条件： 必须经过图中的绿色节点；必须经过图中的两段绿色路段；必须避开图中的红色路段；尽可能以最少的花费到达终点。
- 本例程的框架和步骤同 3.6，这是一个遍历简单路径、判断约束条件的通用框架。
- all(n in path for n in (2,4,7,12,13,14)) 的作用，一是判断路径中是否包括必经点 N7、N12；二是判断路径中是否包括必经边 (2,4)、(13,14) 的各顶点，这不仅可以减小计算量，而且能确保下面使用 index() 查找顶点位置时不会发生错误。
