前面我们已经了解到了无环有向图怎样求关键路径的方法，今天我们来看看无向图怎样求最短路径，这在实际应用过程中的作用很大，不如交通路线图，从出发点到终点，走哪条路用时最短，或者花费最少等问题。

我们先来看单源最短路径的求法。即给定了起点$v$，求从起点出发，到图中各个顶点的最短路径问题。
对于这个问题，迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生的最短路径的算法。

下面介绍迪杰斯特拉算法思想：
（1）、假设用带权的邻接矩阵arcs来表示带权有向图，arcs[i][j]表示弧<$v_i$,$v_j$>上的权值。若<$v_i$,$v_j$>不存在，则置arcs[i][j]为无穷大（在计算机中可用允许的最大值代替。）S为已经找到的从$v$出发的最短路径的终点的集合，他的初始状态为空集。那么，从v出发到图中的其余各顶点（终点）$v_i$可能达到的最短路径长度的初值为：
D[i] = arcs[ Locate Vex(G,v) ][i] $v_i$ 属于 V
（2）、选择$v_j$，使得：D[j] = Min{D[i] | $v_i$ 属于 V-S}，$v_j$就是当前求得的一条从v出发的最短路径的终点。令：S = S 并 {j}
（3）、修改从v出发到集合V-S上任意一点$v_k$可达的最短路径长度。如果：D[j] + arcs[k][k] < D[k]，则修改D[k]为：D[k]= D[j] + arcs[j][k]
（4）、重复操作（2）、（3）共n-1次。由此求得从v到图上其余各顶点的最短路径是依据路径长度递增的序列。

太复杂了，我们来总结描述下：
迪杰斯特拉算法：
假设存在G=<V,E>，源顶点为V0，S={V0},distance[i] 记录V0到i的最短距离，matrix[i][j]记录从i到j的边的权值，即两点之间的距离。
1）从V-S中选择使dist[i]值最小的顶点i，将i加入到U中；
2）更新与i直接相邻顶点的dist值。dist[j]=min{dist[j],dist[i]+matrix[i][j]}
3）直到S=V，所有顶点都包含进来了，算法停止。

Dijkstra算法主要针对的是有向图的单源最短路径问题，且不能出现权值为负的情况！Dijkstra算法类似于贪心算法，其应用根本在于最短路径的最优子结构性质。

最短路径的最优子结构性质：
如果P(i,j)={Vi…Vk…Vs…Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么P(k,s)必定是从k到s的最短路径。

根据其算法思想，确立操作步骤如下：
(1) 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为"起点s到该顶点的距离"[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。
(2) 从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。
(3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。
(4) 重复步骤(2)和(3)，直到遍历完所有顶点。

下面我们用列表法来手动实现这个过程：
我们以下图为例：起点为A

1、找到起始点A,找出从A到图中各点的路径长度：A的邻接点未B和D，其余点距离都为inf(无穷大)

次数/编号	B	C	D	E	F
1	1	max	2	max	max

2、找到最小值是从A到B的距离1，接下来以B为起始点，找到B的邻接点D,C,E：

次数/编号	B	C	D	E	F
1	1	inf	2	inf	inf
2	【1】	min{1+2,inf}=3	min{1+4,2}=2	min{1+3,inf}=4	inf

3、找到第二次最小值为从A到D的距离2，以D为起始点：

次数/编号	B	C	D	E	F
1	1	inf	2	inf	inf
2	【1】	min{1+2,inf}=3	min{1+4,2}=2	min{1+3,inf}=4	inf
3	【1】	3	【2】	min{2+6,4,inf}=4	inf

4、找到第三次的最小值从A到C的值3，以C为起始点：

次数/编号	B	C	D	E	F
1	1	inf	2	inf	inf
2	【1】	min{1+2,inf}=3	min{1+4,2}=2	min{1+3,inf}=4	inf
3	【1】	3	【2】	min{2+6,4,inf}=4	inf
4	【1】	【3】	【2】	min{3+1,4,inf}=4	min{3+4,inf}=7

5、找到第4次最小值是从A到E的值4，以E为起始点：

次数/编号	B	C	D	E	F
1	1	inf	2	inf	inf
2	【1】	min{1+2,inf}=3	min{1+4,2}=2	min{1+3,inf}=4	inf
3	【1】	3	【2】	min{2+6,4,inf}=4	inf
4	【1】	【3】	【2】	min{3+1,4,inf}=4	min{3+4,inf}=7
5	【1】	【3】	【2】	【4】	min{4+2,7,inf} =6

至此所有的顶点全部遍历完成：

次数/编号	B	C	D	E	F
1	1	inf	2	inf	inf
2	【1】	min{1+2,inf}=3	min{1+4,2}=2	min{1+3,inf}=4	inf
3	【1】	3	【2】	min{2+6,4,inf}=4	inf
4	【1】	【3】	【2】	min{3+1,4,inf}=4	min{3+4,inf}=7
5	【1】	【3】	【2】	【4】	【6】

那么从表中我们就能够得到：
A到B，到C，到D，到E，到F的最短路径依次为1，3，2，4，6

现在我们得到了从A到各个节点的最短路径的值，那么问题来了，怎样得到最短路径呢？

例如，现在我们要求出从A到F的最短路径：
我们使用上一跳存储列表法来实现，初始化都为-1，-1表示直连。

名称/编号	B	C	D	E	F
cost	1	3	2	4	6
last—top	-1	-1	-1	-1	-1

1、首先是顶点B，因为B和A直连，所以，直接赋值为-1

名称/编号	B	C	D	E	F
cost	1	3	2	4	6
last—top	【-1】	-1	-1	-1	-1

2、接下来是顶点C，A要到达顶点C，距离为3，必须经过顶点B，所以C的上一跳为B

名称/编号	B	C	D	E	F
cost	1	3	2	4	6
last—top	【-1】	B	-1	-1	-1

3、接下来是点D，D和A直连，直接赋值为-1

名称/编号	B	C	D	E	F
cost	1	3	2	4	6
last—top	【-1】	B	【-1】	-1	-1

4、接下来是点E，A要到达E,距离为4，必须经过顶点B，所以E的上一跳为B

名称/编号	B	C	D	E	F
cost	1	3	2	4	6
last—top	【-1】	B	【-1】	B	-1

5、接下来是点F，A要到达顶点F，距离为6，必须经过顶点E,所以F的上一跳为E

名称/编号	B	C	D	E	F
cost	1	3	2	4	6
last—top	【-1】	B	【-1】	B	E

那么现在我们要从A到F，最短路径是什么呢？
过程是这样的要到F，得经过E；要到E，得经过B；要到B，得经过A。
于是，从A到F的最短路径为：A —> B —> E —> F

python">def Dijkstra(network, s, d):  # 迪杰斯特拉算法算s-d的最短路径，并返回该路径和值
    print("Start Dijstra Path……")
    path = []  # 用来存储s-d的最短路径
    n = len(network)  # 邻接矩阵维度，即节点个数
    fmax = float('inf')
    w = [[0 for _ in range(n)] for j in range(n)]  # 邻接矩阵转化成维度矩阵，即0→max

    book = [0 for _ in range(n)]  # 是否已经是最小的标记列表
    dis = [fmax for i in range(n)]  # s到其他节点的最小距离
    book[s - 1] = 1  # 节点编号从1开始，列表序号从0开始
    midpath = [-1 for i in range(n)]  # 上一跳列表
    for i in range(n):
      for j in range(n):
        if network[i][j] != 0:
          w[i][j] = network[i][j]  # 0→max
        else:
          w[i][j] = fmax
        if i == s - 1 and network[i][j] != 0:  # 直连的节点最小距离就是network[i][j]
          dis[j] = network[i][j]
    for i in range(n - 1):  # n-1次遍历，除了s节点
      min = fmax
      for j in range(n):
        if book[j] == 0 and dis[j] < min:  # 如果未遍历且距离最小
          min = dis[j]
          u = j
      book[u] = 1
      for v in range(n):  # u直连的节点遍历一遍
        if dis[v] > dis[u] + w[u][v]:
          dis[v] = dis[u] + w[u][v]
          midpath[v] = u + 1  # 上一跳更新
    j = d - 1  # j是序号
    path.append(d)  # 因为存储的是上一跳，所以先加入目的节点d，最后倒置
    while (midpath[j] != -1):
      path.append(midpath[j])
      j = midpath[j] - 1
    path.append(s)
    path.reverse()  # 倒置列表
    print("path:",path)
    # print(midpath)
    print("dis:",dis)
    # return path

network = [[0, 1, 0, 2, 0, 0],
           [1, 0, 2, 4, 3, 0],
           [0, 2, 0, 0, 1, 4],
           [2, 4, 0, 0, 6, 0],
           [0, 3, 1, 6, 0, 2],
           [0, 0, 4, 0, 2, 0]]
Dijkstra(network, 1, 6)

运行结果：

python">Start Dijstra Path……
path: [1, 2, 5, 6]
dis: [2, 1, 3, 2, 4, 6]