Python⼩⽩的数学建模课-16.最短路径算法
最短路径问题是图论研究中的经典算法问题，⽤于计算图中⼀个顶点到另⼀个顶点的最短路径。
在图论中，最短路径长度与最短路径距离却是不同的概念和问题，经常会被混淆。
求最短路径长度的常⽤算法是 Dijkstra 算法、Bellman-Ford 算法和Floyd 算法，另外还有启发式算法 A*。
带你从数模⼩⽩成为国赛达⼈。
1. 最短路径问题
最短路径问题是图论研究中的经典算法问题，⽤于计算图中⼀个顶点到另⼀个顶点的最短路径。
最短路径问题有⼏种形式：确定起点的最短路径，确定终点的最短路径，确定起点和终点的最短路径，全局最短路径问题。
1.1 最短路径长度与最短路径距离
在⽇常⽣活中，最短路径长度与最短路径距离好像并没什么区别。但在图论中最短路径长度与最短路径
距离却是不同的概念和问题，经常会被混淆。
图论中有⽆权图和有权图，⽆权图中的边没有权，赋权图的边带有权，可以表⽰距离、时间、费⽤或其它指标。在问题⽂字描述中，往往并不直接指出是⽆权图还是有权图，这时就要特别注意最短路径与最短加权路径的区别。
路径长度是把每个顶点到相邻顶点的长度记为 1，⽽不是指这两个顶点之间道路的距离——两个顶点之间的道路距离是连接边的权（weight）。
通俗地说，路径长度可以认为是飞⾏棋的步数，或者公交站点的站数，相邻顶点之间为⼀步，相隔⼏个顶点就是⼏站。路径长度是从路径起点到终点的步数，计算最短路径是要计算从起点到终点步数最少的路径。
如果问题不涉及相邻顶点间的距离，要计算从起点到终点的最短路径及对应的最短路径长度，是指这条路径从起点到终点有⼏步（站），在图论中称为最短路径长度。但是，如果问题给出相邻顶点之间的道路长度或距离，姑且称为各路段的距离，要计算从起点到终点的最短路径及对应的最短距离，显然并不是要找经过最少步数的路径，⽽是在找路径中各路段的距离之和最⼩的路径，在图论中称为最短加权路径长度——这⾥权重是路段距离。
相邻顶点的连接边的权，不仅可以是路段距离，也可以是时间、费⽤等指标。问题就变成寻求最短时间、最低成本的路径，这实际上也是最短加权路径长度问题。
1.2 最短路径的常⽤算法
求解最短路径长度的常⽤算法是 Dijkstra 算法、Bellman-Ford 算法和Floyd 算法，另外还有启发式算法 A*。
1.2.1 Dijkstra 算法
Dijkstra 算法是经典的最短路径算法，在数据结构、图论、运筹学中都是教学的基本算法。有趣的是，在数据结构中 Dijkstra 算法通常是按贪⼼法讲述，⽽在运筹学中则被认为是动态规划法。
Dijkstra算法从起点开始，采⽤贪⼼法策略，每次遍历距离起点最近且未访问过的邻接顶点，层层扩展直到终点为⽌。
Dijkstra算法可以求出加权最短路径的最优解，算法的时间复杂度为O(n^2)。如果边数远⼩于 n^2，可以⽤堆结构将复杂度降
为O((m+n)log(n))。
Dijkstar算法不能处理负权边，这是由于贪⼼法的选择规则决定的。
1.2.2 Bellman-Ford 算法
Bellman-Ford 算法是求含负权图的单源最短路径算法。算法原理是对图进⾏ V-1次松弛操作，得到所有可能的最短路径。
Bellman-Ford 算法可以处理负权边。其基本操作“拓展”是在深度上搜索，⽽“松弛”操作则在⼴度上搜索，因此可以对负权边进⾏操作⽽不影响结果。
Bellman-Ford 算法的效率很低，时间复杂度⾼达O(V*E)，V、E 分别是顶点和边的数量。SPFA 是 Bellman-Ford 的队列优化，通过维护⼀个队列极⼤地减少了重复计算，时间复杂度为O(k*E) 。
Dijkstra 算法在求解过程中，起点到各顶点的最短路径求出后就不变了。Bellman算法在求解过程中，每次循环都要修改所有顶点间的距离，起点到各顶点最短路径⼀直要到算法结束才确定。
1.2.3 Floyd 算法
Floyd 算法⼜称插点法，运⽤动态规划思想求解有权图中多源点之间最短路径问题。算法从图的带权邻接矩阵开始，递归地进⾏ n 次更新得到图的距离矩阵，进⽽可以得到最短路径节点矩阵。
Floyd 算法的时间复杂度为O(n^3)，空间复杂度为O(n^2)。算法时间复杂度较⾼，不适合计算⼤量数据。Floyd 算法的优点是可以⼀次性求解任意两个节点之间的最短距离，对于稠密图的效率⾼于执⾏ V 次 Dijkstra算法。
Floyd 算法可以处理负权边。
Floyd 算法号称只有 5⾏代码，我们来欣赏⼀下：
for(k=0;k<n;k++)//中转站0~k
for(i=0;i<n;i++) //i为起点
for(j=0;j<n;j++) //j为终点
if(d[i][j]>d[i][k]+d[k][j])//松弛操作
d[i][j]=d[i][k]+d[k][j];
1.2.4 A* 算法
A*算法是⼀种静态路⽹中求解最短路径最有效的直接搜索⽅法。
A*算法是启发式算法，采⽤最佳优先（Best-first）搜索策略，基于估价函数对每个搜索位置的评估结果，猜测最好的位置优先进⾏搜索。A*算法极⼤地减少了低质量的搜索路径，因⽽搜索效率很⾼，⽐传统的路径规划算法实时性更⾼、灵活性更强；但是，A*算法找到的是相对最优路径，不是绝对的最短路径，适合⼤规模、实时性⾼的问题。
1.3 最短路径算法的选择
1. 需要求解任意两个节点之间的最短距离，使⽤ Floyd 算法；
2. 只要求解单源最短路径问题，有负权边时使⽤ Bellman-Ford 算法，没有负权边时使⽤ Dijkstra 算法；
3. A*算法找到的是相对最优路径，适合⼤规模、实时性⾼的问题。
2. NetworkX 中的最短路径算法
NetworkX 提供了丰富的最短路径函数，除了常见的 Dijkstra 算法、Bellman-ford 算法、Floyd Warshall 算法和 A*算法，还有 Goldbery-Radzik 算法和 Johnson 算法。其中，Bellman-ford 算法函数使⽤的是队列改进算法，即以 SPFA 算法实现。
2.1 ⽆向图和有向图的最短路径求解函数
函数功能
shortest_path(G[, source, target, weight,...])计算图中的最短路径
all_shortest_paths(G, source, target[,...])计算图中所有最短的简单路径
shortest_path_length(G[, source, target, ...])计算图中的最短路径长度
average_shortest_path_length(G[, weight, method])计算平均最短路径长度
其中，最基本的求解最短路径函数 shortest() 和最短路径长度 shortest_path_length() 是 ‘dijkstra’ 算法和 ‘bellman-ford’ 算法的集成接⼝，可以通过 method='dijkstra' 选择不同的算法。
shortest_path(G, source=None, target=None, weight=None, method='dijkstra')
shortest_path_length(G, source=None, target=None, weight=None, method='dijkstra')
主要参数：
G(NetworkX graph)：图。
source (node)：起点。
target (node)：终点。
weight (string or function)：参数为字符串(string)时，按该字符串查找边的属性作为权重；如果该字符串对应的边属性不存在，则权重置为 1；参数为函数时，边的权重是函数的返回值。
method [string, optional (default = ‘dijkstra’)]：⽀持的选项为 ‘dijkstra’, ‘bellman-ford’。
2.2 ⽆权图最短路径算法
函数功能
single_source_shortest_path(G, source[,cutoff])计算从源到所有可达节点的最短路径
single_source_shortest_path_length(G,source)计算从源到所有可达节点的最短路径长度
single_target_shortest_path(G, target[,cutoff])计算从所有可达节点到⽬标的最短路径
single_target_shortest_path_length(G,target)计算从所有可达节点到⽬标的最短路径长度
函数功能
all_pairs_shortest_path(G[, cutoff])计算所有节点之间的最短路径
all_pairs_shortest_path_length(G[, cutoff])计算所有节点之间的最短路径长度
2.3 有权图最短路径算法
函数功能
dijkstra_path(G, source, target[, weight])计算从源到⽬标的最短加权路径
dijkstra_path_length(G, source, target[,weight])计算从源到⽬标的最短加权路径长度
all_pairs_dijkstra_path(G[, cutoff, weight])计算所有节点之间的最短加权路径
all_pairs_dijkstra_path_length(G[, cutoff,... ])计算所有节点之间的最短加权路径长度
bellman_ford_path(G, source, target[, weight])计算从源到⽬标的最短路径
bellman_ford_path_length(G, source, target)计算从源到⽬标的最短路径长度
all_pairs_bellman_ford_path(G[, weight])计算所有节点之间的最短路径
all_pairs_bellman_ford_path_length(G[,weight])计算所有节点之间的最短路径长度
floyd_warshall(G[, weight])⽤ Floyd 法计算所有节点之间的最短路径长度
floyd_warshall_numpy(G[, nodelist, weight])⽤ Floyd 法计算所有指定节点之间的最短路径长度
3. NetworkX 中的 Dijkstra 算法
NetworkX 中关于 Dijkstra 算法提供了 13 个函数，很多函数的功能是重复的。这⾥只介绍最基本的函数 dijkstra_path() 和
dijkstra_path_length()。
3.1 dijkstra_path() 和 dijkstra_path_length() 使⽤说明
dijkstra_path() ⽤于计算从源到⽬标的最短加权路径，dijkstra_path_length() ⽤于计算从源到⽬标的最短加权路径长度。
dijkstra_path(G, source, target, weight='weight')
dijkstra_path_length(G, source, target, weight='weight')
主要参数：
G(NetworkX graph)：图。
source (node)：起点。
target (node)：终点。
weight (string or function)：参数为字符串(string)时，按该字符串查找边的属性作为权重；如果该字符串对应的边属性不存在，则权重置为1；参数为函数时，边的权重是函数的返回值。
苦涩返回值：
dijkstra_path() 的返回值是最短加权路径中的节点列表，数据类型为list。
dijkstra_path_length() 的返回值是最短加权路径的长度（路径中的边的权重之和）。
3.2 例题 1：⽆向图的最短路径问题
例题 1：已知如图的有权⽆向图，求顶点 v1 到顶点 v11 的最短路径。
本问题来⾃：司守奎、孙兆亮，数学建模算法与应⽤（第2版），P43，例4.3，国防⼯业出版社。
程序说明：
初二物理课本1. 图的输⼊。本例的问题是稀疏的有权⽆向图，使⽤ add_weighted_edges_from() 函数可以⽤列表形式向图中添加多条赋权边，每个赋
权边以元组 (node1,node2,weight) 表⽰。
2. 图的绘制。使⽤ nx.draw() 绘图时，默认的顶点位置可能并不理想，可以通过 pos 指定顶点位置。
3. 绘制边的属性。使⽤ nx.draw_networkx_edge_labels() 可以绘制边的属性，例程中选择显⽰权重属性。
4. 使⽤ dijkstra_path() 和 dijkstra_path_length() 求指定顶点之间的最短加权路径和最短加权路径长度。
3.3 dijkstra_path() 算法例程
# mathmodel16_v1.py
# Demo16 of mathematical modeling algorithm
# Demo of shortest path with NetworkX
# Copyright 2021 YouCans, XUPT
# Crated：2021-07-07
import matplotlib.pyplot as plt # 导⼊ Matplotlib ⼯具包
import networkx as nx # 导⼊ NetworkX ⼯具包
# 问题 1：⽆向图的最短路问题（司守奎，数学建模算法与应⽤，P43，例4.3）
G1 = nx.Graph() # 创建：空的⽆向图
G1.add_weighted_edges_from([(1,2,2),(1,3,8),(1,4,1),
(2,3,6),(2,5,1),
(3,4,7),(3,5,5),(3,6,1),(3,7,2),
(4,7,9),
(5,6,3),(5,8,2),(5,9,9),
(6,7,4),(6,9,6),
(7,9,3),(7,10,1),
(8,9,7),(8,11,9),
(9,10,1),(9,11,2),
补肾药材(10,11,4)]) # 向图中添加多条赋权边: (node1,node2,weight)
print('nx.info:',G1.nodes) # 返回图的基本信息
# 两个指定顶点之间的最短加权路径
minWPath_v1_v11 = nx.dijkstra_path(G1, source=1, target=11) # 顶点 1 到顶点 11 的最短加权路径
print("顶点 v1 到顶点 v11 的最短加权路径: ", minWPath_v1_v11)
# 两个指定顶点之间的最短加权路径的长度
lMinWPath_v1_v11 = nx.dijkstra_path_length(G1, source=1, target=11) # 最短加权路径长度
print("顶点 v1 到顶点 v11 的最短加权路径长度: ", lMinWPath_v1_v11)
pos = {1: (0,4), 2: (5,7), 3: (5,4), 4: (5,1), 5: (10,7), 6: (10,4), 7: (10,1),
8: (15,7), 9: (15,4), 10: (15,1), 11: (20,4)} # 指定顶点位置
labels = nx.get_edge_attributes(G1, 'weight') # 设置边的 labels 为 ‘weight'
nx.draw(G1, pos, with_labels=True, font_color='w') # 绘制⽆向图
nx.draw_networkx_edge_labels(G1, pos, edge_labels=labels, font_color='c') # 显⽰边的权值
plt.show()
3.4 程序运⾏结果
nx.info: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
顶点 v1 到顶点 v11 的最短加权路径: [1, 2, 5, 6, 3, 7, 10, 9, 11]
顶点 v1 到顶点 v11 的最短加权路径长度: 13
4. NetworkX 中的 Bellman-Ford 算法
NetworkX 中关于 Bellman-Ford 算法提供了多个函数，这⾥只介绍最基本的函数 bellman_ford_path() 和 bellman_ford_path_length()。
4.1 bellman_ford_path() 和 bellman_ford_path_length() 使⽤说明
bellman_ford_path() ⽤于计算从源到⽬标的最短加权路径，bellman_ford_path_length() ⽤于计算从源到⽬标的最短加权路径长度。
bellman_ford_path(G, source, target, weight='weight')
bellman_ford_path_length(G, source, target, weight='weight')
主要参数：
G(NetworkX graph)：图。
source (node)：起点。
target (node)：终点。
weight (string)：按字符串查找边的属性作为权重。默认值为权重 'weight'。
返回值：
bellman_ford_path() 的返回值是最短加权路径中的节点列表，数据类型为list。
bellman_ford_path_length() 的返回值是最短加权路径的长度（路径中的边的权重之和）。
12生肖守护佛4.2 例题 2：城市间机票价格问题
例题 2：城市间机票价格问题。
已知 6个城市之间的机票票价如矩阵所⽰（⽆穷⼤表⽰没有直航），求城市 c0 到其它城市 c1...c5 的票价最便宜的路径及票价。
\begin{bmatrix} 0 & 50 & \infty & 40 & 25 & 10\\ 50 & 0 & 15 & 20 & \infty & 25\\ \infty & 15 & 0 & 10 & 20 & \infty\\ 40 & 20 & 10 & 0 & 10 & 25\\ 25 & \infty & 20 & 10 & 0 & 55\\ 10 & 25 & \infty & 25 & 55 & 0\\ \end{bmatrix}
本案例问题改编⾃：司守奎、孙兆亮，数学建模算法与应⽤（第2版），P41，例4.1，国防⼯业出版社。
程序说明
1. 图的输⼊。使⽤ pandas 中 DataFrame 读取数据⽂件⾮常⽅便，本例中以 pandas 输⼊顶点邻接矩阵，使⽤
nx.from_pandas_adjacency(dfAdj) 转换为 NetworkX 的图。
2. 邻接矩阵。邻接矩阵 dfAdj (i,j) 的值表⽰连接顶点 i、j 的边的权值， dfAdj (i,j) = 0 表⽰ i、j 不相邻，本例中表⽰没有直航。
3. 最短路径与最短路径长度。nx.shortest_path() 返回最短路径。nx.shortest_path_length() 返回最短路径长度，本例中可以理解为从起点
细致的拼音到终点的乘机次数：1 表⽰直航，2 表⽰中转⼀次。
4. 最短加权路径长度。nx.bellman_ford_path_length() 返回最短加权路径长度，本例中权重为票价，最短加权路径长度即为两点间最便
宜的直航或中转的机票票价。
通过本案例，可以直观地理解最短路径长度与最短加权路径长度的区别。
4.3 bellman_ford_path() 算法例程
# mathmodel16_v1.py
# Demo16 of mathematical modeling algorithm
肚脐眼流脓# Demo of shortest path with NetworkX
# Copyright 2021 YouCans, XUPT
# Crated：2021-07-07
import pandas as pd
import matplotlib.pyplot as plt # 导⼊ Matplotlib ⼯具包
import networkx as nx # 导⼊ NetworkX ⼯具包
# 问题 2：城市间机票价格问题（司守奎，数学建模算法与应⽤，P41，例4.1）
# # 从Pandas数据格式（顶点邻接矩阵）创建 NetworkX 图
# # from_pandas_adjacency(df, create_using=None) # 邻接矩阵，n⾏*n列，矩阵数据表⽰权重
dfAdj = pd.DataFrame([[0, 50, 0, 40, 25, 10], # 0 表⽰不邻接，
[50, 0, 15, 20, 0, 25],
关于奋斗的例子[0, 15, 0, 10, 20, 0],
[40, 20, 10, 0, 10, 25],
[25, 0, 20, 10, 0 ,55],
[10, 25, 0, 25, 55, 0]])
G2 = nx.from_pandas_adjacency(dfAdj) # 由 pandas 顶点邻接矩阵创建 NetworkX 图
# 计算最短路径：注意最短路径与最短加权路径的不同
# 两个指定顶点之间的最短路径
minPath03 = nx.shortest_path(G2, source=0, target=3) # 顶点 0 到顶点 3 的最短路径
lMinPath03 = nx.shortest_path_length(G2, source=0, target=3) #最短路径长度
print("顶点 0 到 3 的最短路径为：{}，最短路径长度为：{}".format(minPath03, lMinPath03))
# 两个指定顶点之间的最短加权路径
minWPath03 = nx.bellman_ford_path(G2, source=0, target=3) # 顶点 0 到顶点 3 的最短加权路径
# 两个指定顶点之间的最短加权路径的长度
lMinWPath03 = nx.bellman_ford_path_length(G2, source=0, target=3) #最短加权路径长度
print("顶点 0 到 3 的最短加权路径为：{}，最短加权路径长度为：{}".format(minWPath03, lMinWPath03))
for i in range(1,6):
minWPath0 = nx.bellman_ford_path(G2, source=0, target=i) # 顶点 0 到其它顶点的最短加权路径
lMinPath0 = nx.bellman_ford_path_length(G2, source=0, target=i) #最短加权路径长度
print("城市 0 到城市 {} 机票票价最低的路线为: {}，票价总和为：{}".format(i, minWPath0, lMinPath0))
nx.draw_shell(G2, with_labels=True, node_color='r', edge_color='b', font_color='w', width=2)
plt.show()
4.4 程序运⾏结果掏宝手机
顶点 0 到 3 的最短路径为：[0, 3]，最短路径长度为：1
顶点 0 到 3 的最短加权路径为：[0, 4, 3]，最短加权路径长度为：35
城市 0 到城市 1 机票票价最低的路线为: [0, 5, 1]，票价总和为：35
城市 0 到城市 2 机票票价最低的路线为: [0, 4, 2]，票价总和为：45
城市 0 到城市 3 机票票价最低的路线为: [0, 5, 3]，票价总和为：35
城市 0 到城市 4 机票票价最低的路线为: [0, 4]，票价总和为：25
城市 0 到城市 5 机票票价最低的路线为: [0, 5]，票价总和为：10
5. 总结
1. 最短路径问题是图论研究中的经典算法问题，⽤于计算图中⼀个顶点到另⼀个顶点的最短路径。
2. 在图论中，求最短路径长度是要计算从起点到终点步数最少的路径，⽽求最短路径距离是要计算最短加权路径长度。从例 2的运⾏结
果可以对⽐⼆者的区别。
3. 求最短路径长度的常⽤算法是 Dijkstra 算法、Bellman-Ford 算法和Floyd 算法，另外还有启发式算法 A*。
4. 对于稀疏的图推荐使⽤列表形式添加赋权边，对于稠密图、完全图建议使⽤ DtaFrame 读取数据⽂件后再转换为 NetworkX 格式。
