Dijkstra算法的带权有向图最短路径问题求解Python实现

Dijkstra算法简介

Dijkstra算法是一种贪心算法，它先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径，直到求出从源点到其他各个顶点的最短路径。

具体的步骤

下面的介绍来自《趣学算法》

另一个例子用Python实现

用Python和Numpy实现寻找任意两点之间最小路径的算法，并用下图进行测试, 得到节点s和t之间的最短路径。 

对于上面这个图，Dijkstra算法的步骤如下：

1.先找到距离s点最近的点，即w

2.然后看与w相连接的点通过w再到那个点的距离近还是直接从s到这个点的距离近，由上图我们可以知道，与w相连的点是t和z，而t和z并不与s直接相连，因此更新最短距离数组和前驱数组

3.接着对距离s点第二近的点“X”重复第二个步骤，直到都执行完毕。（目的是看与“X”相连的点能否借助“X”获得更近的路径，即经过“X”，这就是上面的“借东风”）

下面的代码中，点s,v,u,w,z,t分别表示为点1,2,3,4,5,6

1.  
   import numpy as np
2.  
   import copy
3.  
    
4.  
   def main():
5.  
   #无穷大
6.  
   infinity = float('inf')
7.  
   a = infinity
8.  
   #构建邻接矩阵
9.  
   adjacency_matrix = np.array([[a,6,5,3,a,a],
10.  
    [a,a,a,1,a,3],
11.  
    [a,a,a,1,2,a],
12.  
    [a,a,a,a,9,7],
13.  
    [a,a,a,a,a,5],
14.  
    [a,a,a,a,a,a]])
15.  
    #构建距离数组
16.  
    dist = np.array([0,6,5,3,a,a])
17.  
    #构建前驱数组
18.  
    precursor = np.array([-1,1,1,1,-1,-1])
19.  
    #初始集合
20.  
    S = {1}
21.  
    V = {1,2,3,4,5,6}
22.  
    V_subtract_S = V - S
23.  
     
24.  
    for i in range(len(V_subtract_S)-1):
25.  
    dist_copy = []
26.  
    V_subtract_S_list = list(V_subtract_S)
27.  
    for j in V_subtract_S:
28.  
    dist_copy.append(dist[j - 1])
29.  
    min_index = dist_copy.index(min(dist_copy)) # 查找dist_copy中最小的元素的位置
30.  
    S.add(V_subtract_S_list[min_index])
31.  
    current_node = V_subtract_S_list[min_index]
32.  
    V_subtract_S = V - S
33.  
     
34.  
    for j in V_subtract_S:
35.  
    dist_copy.append(dist[j - 1])
36.  
    for j in range(adjacency_matrix.shape[1]):
37.  
    if adjacency_matrix[current_node-1][j] < a:
38.  
    if dist[current_node-1] adjacency_matrix[current_node-1][j] < dist[j]:
39.  
    dist[j] = dist[current_node-1] adjacency_matrix[current_node-1][j]
40.  
    precursor[j] = current_node
41.  
     
42.  
    #打印最佳路径
43.  
    temp = 1
44.  
    path = []
45.  
    path.insert(0, 6)
46.  
    precursor = list(precursor)
47.  
    front_code = precursor[5]
48.  
    while temp:
49.  
    path.insert(0,front_code)
50.  
    #front_code的数字对应的另一个节点
51.  
    front_code_index = path[0] - 1
52.  
    front_code = precursor[front_code_index]
53.  
    if front_code == 1:
54.  
    temp = 0
55.  
    path.insert(0,1)
56.  
    for i in path:
57.  
    if i == 1:
58.  
    path[path.index(i)] = 's'
59.  
    if i == 2:
60.  
    path[path.index(i)] = 'v'
61.  
    if i == 3:
62.  
    path[path.index(i)] = 'u'
63.  
    if i == 4:
64.  
    path[path.index(i)] = 'w'
65.  
    if i == 5:
66.  
    path[path.index(i)] = 'z'
67.  
    if i == 6:
68.  
    path[path.index(i)] = 't'
69.  
     
70.  
    print(path)

运行结果：

这篇好文章是转载于：学新通技术网