一、最短路径问题(shortest path problem)
最短路径问题是图论研究中一个经典算法问题，旨在寻找图中两节点或单个节点到其他节点之间的最短路径。根据问题的不同，算法的具体形式包括：
确定起点的最短路径问题，即给定起始节点，求该节点到其他剩余节点的最短路径，适合使用Dijkstra算法；
确定终点的最短路径问题，即给定终点，求其他节点到该终点的最短路径。在无向图中，该问题与确定起点的问题等价；在有向图中，问题等价于把所有路径方向反转的确定起点的问题；
确定起点终点的最短路径问题，即给定起点和终点，求两节点之间的最短路径；
全局最短路径问题，即求图中所有节点之间的最短路径，适合使用Floyd-Warshall算法。
常用的最短路径算法包括：Dijkstra算法，A
算法，Bellman-Ford算法，SPFA算法(Bellman-Ford算法的改进版本)，Floyd-Warshall算法，Johnson算法以及Bi-direction BFS算法。本文将重点介绍Dijkstra算法的原理以及实现。
二、Dijkstra算法介绍
1. 算法概览
Dijkstra算法，翻译作戴克斯特拉算法或迪杰斯特拉算法，于1956年由荷兰计算机科学家艾兹赫尔.戴克斯特拉提出，用于解决赋权有向图的单源最短路径问题。所谓单源最短路径问题是指确定起点，寻找该节点到图中任意节点的最短路径，算法可用于寻找两个城市中的最短路径或是解决著名的旅行商问题。
问题描述：在无向图
中，
为图节点的集合，
为节点之间连线边的集合。假设每条边
的权重为
，找到由顶点
到其余各个节点的最短路径(单源最短路径)。
2. 算法描述
为带权无向图，图中顶点
分为两组，第一组为已求出最短路径的顶点集合(用
表示)。初始时
只有源点，当求得一条最短路径时，便将新增顶点添加进
，直到所有顶点加入
中，算法结束。第二组为未确定最短路径顶点集合(用
表示)，随着
中顶点增加，
中顶点逐渐减少。
初始化：
只包含起点
，
包含
外的其他顶点。
中的距离为起点
到顶点的距离。若
与
相邻，则
中顶点
距离为
的边缘权重；若
与
不相邻，则
的距离为
;
更新
和
：从
中选出距离值最小的顶点
，并将顶点
添加至
；同时，从
中移除
；
更新
中顶点到起点
的距离：由于
中添加了
，利用
进一步更新
到其他顶点的距离，存在
的可能性；
反复迭代：重复第二步和第三步，直到遍历完所有节点。
3. 算法示例
以下图为例，对Dijkstra算法的工作流程进行演示(以顶点
为起点)：
图1. 有权无向图G
注：
01)
是已计算出最短路径的顶点集合；
02)
是未计算出最短路径的顶点集合；
03)
表示顶点
到顶点
的最短距离为3
第1步：选取顶点
添加进
图2. 第1步
第2步：选取顶点
添加进
，更新
中顶点最短距离
图3. 第2步
第3步：选取顶点
添加进
，更新
中顶点最短距离
图4. 第3步
第4步：选取顶点
添加进
，更新
中顶点最短距离
图5. 第4步
第5步：选取顶点
添加进
，更新
中顶点最短距离
图6. 第5步
第6步：选取顶点
添加进
，更新
中顶点最短距离
图7. 第6步
第7步：选取顶点
添加进
，更新
中顶点最短距离
图8. 第7步
三、Dijkstra算法的R及Python软件实现
1. R实现Dijkstra算法：igraph包中shortest.paths函数
示例：node编号1-7分别代表A,B,C,D,E,F,G
require(igraph)
graph_matrix
"node x1 x2 x3 x4 x5 x6 x7
1 0 12 NA NA NA 16 14
2 12 0 10 NA NA 7 NA
3 NA 10 0 3 5 6 NA
4 NA NA 3 0 4 NA NA
5 NA NA 5 4 0 2 8
6 16 7 6 NA 2 0 9
7 14 NA NA NA 8 9 0
", header=T))
nms
mat
colnames(mat)
mat[is.na(mat)]
# create graph from adjacency matrix
g
# Get all path distances
(s.paths
(s.paths
(s.paths
1 2 3 4 5 6 7
1 0 12 22 22 18 16 14
2 12 0 10 13 9 7 16
3 22 10 0 3 5 6 13
4 22 13 3 0 4 6 12
5 18 9 5 4 0 2 8
6 16 7 6 6 2 0 9
7 14 16 13 12 8 9 0
(s.paths
1 2 3 4 5 6 7
4 22 13 3 0 4 6 12
2. Python语言实现Dijkstra算法：networkx 模块
示例：
from dijkstar import Graph, find_path
graph=Graph()
graph.add_edge(1,2,{'cost':12})
graph.add_edge(1,6,{'cost':16})
graph.add_edge(1,7,{'cost':14})
graph.add_edge(2,3,{'cost':10})
graph.add_edge(2,6,{'cost':7})
graph.add_edge(2,1,{'cost':12})
graph.add_edge(3,2,{'cost':10})
graph.add_edge(3,4,{'cost':3})
graph.add_edge(3,5,{'cost':5})
graph.add_edge(3,6,{'cost':6})
graph.add_edge(4,3,{'cost':3})
graph.add_edge(4,5,{'cost':4})
graph.add_edge(3,5,{'cost':5})
graph.add_edge(3,6,{'cost':6})
graph.add_edge(4,3,{'cost':3})
graph.add_edge(4,5,{'cost':4})
graph.add_edge(5,3,{'cost':5})
graph.add_edge(5,4,{'cost':4})
graph.add_edge(5,6,{'cost':2})
graph.add_edge(5,7,{'cost':8})
graph.add_edge(6,1,{'cost':16})
graph.add_edge(6,2,{'cost':7})
graph.add_edge(6,3,{'cost':6})
graph.add_edge(6,5,{'cost':2})
graph.add_edge(6,7,{'cost':9})
graph.add_edge(7,1,{'cost':14})
graph.add_edge(7,5,{'cost':8})
graph.add_edge(7,6,{'cost':9})
cost_func = lambda u, v, e, prev_e: e['cost']
find_path(graph, 4, 7, cost_func=cost_func)
找到D(4)到G(7)的最短路径：
PathInfo(nodes=[4, 5, 7], edges=[{'cost': 4}, {'cost': 8}], costs=[4, 8], total_cost=12)
参考资料：
