dijkstra最短路算法

Halcom

dijkstra最短路算法
给定终点src，从全部可能的起点出发，得到全部的最短路径。

1. def dijkstra(graph,src):
   
2.     length = len(graph)
   
3.     type_ = type(graph)
   
4.     if type_ == list:
   
5.         nodes = [i for i in xrange(length)]
   
6.     elif type_ == dict:
   
7.         nodes = graph.keys()
   
8. 
   
9.     visited = [src]
   
10.     path = {src:{src:[]}}
    
11.     nodes.remove(src)
    
12.     distance_graph = {src:0}
    
13.     pre = next = src
    
14. 
    
15.     while nodes:
    
16.         distance = float('inf')
    
17.         for v in visited:
    
18.              for d in nodes:
    
19.                 new_dist = graph[src][v] + graph[v][d]
    
20.                 if new_dist <= distance:
    
21.                     distance = new_dist
    
22.                     next = d
    
23.                     pre = v
    
24.                     graph[src][d] = new_dist
    
25. 
    
26. 
    
27.         path[src][next] = [i for i in path[src][pre]]
    
28.         path[src][next].append(next)
    
29. 
    
30.         distance_graph[next] = distance
    
31. 
    
32.         visited.append(next)
    
33.         nodes.remove(next)
    
34. 
    
35.     return distance_graph, path
    
36. 
    
37. 
    
38. if __name__ == '__main__':
    
39.     graph_list = [   [0, 2, 1, 4, 5, 1],
    
40.             [1, 0, 4, 2, 3, 4],
    
41.             [2, 1, 0, 1, 2, 4],
    
42.             [3, 5, 2, 0, 3, 3],
    
43.             [2, 4, 3, 4, 0, 1],
    
44.             [3, 4, 7, 3, 1, 0]]
    
45. 
    
46.     graph_dict = {  "s1":{"s1": 0, "s2": 2, "s10": 1, "s12": 4, "s5":3},
    
47.                     "s2":{"s1": 1, "s2": 0, "s10": 4, "s12": 2, "s5":2},
    
48.                     "s10":{"s1": 2, "s2": 1, "s10": 0, "s12":1, "s5":4},
    
49.                     "s12":{"s1": 3, "s2": 5, "s10": 2, "s12":0,"s5":1},
    
50.                     "s5":{"s1": 3, "s2": 5, "s10": 2, "s12":4,"s5":0},
    
51.     }
    
52. 
    
53.     distance, path = dijkstra(graph_list, 2)
    
54.     #print distance, '\n', path
    
55.     distance, path = dijkstra(graph_dict, 's1')
    
56.     print distance, '\n', path

复制代码

参考：[1]graph_algorithm

Halcom

1. # 起点starpoint，终点src
   
2. def dijkstra_st(graph, startpoint, src):
   
3.     length = len(graph)
   
4. #    type_ = type(graph)
   
5. #    if type_ == list:
   
6. #        nodes = [i for i in xrange(length)]
   
7. #    elif type_ == dict:
   
8. #        nodes = graph.keys()
   
9.     if isinstance(graph, list):
   
10.         nodes = [i for i in range(length)]
    
11.     elif isinstance(graph, dict):
    
12.         nodes = graph.keys()
    
13. 
    
14.     visited = [src]
    
15.     path = {src:{src:[]}}
    
16.     nodes.remove(src)
    
17.     distance_graph = {src:0}
    
18.     pre = next = src
    
19. 
    
20.     while nodes:
    
21.         distance = float('inf')
    
22.         for v in visited:
    
23.              for d in nodes:
    
24.                 new_dist = graph[src][v] + graph[v][d]
    
25.                 if new_dist <= distance:
    
26.                     distance = new_dist
    
27.                     next = d
    
28.                     pre = v
    
29.                     graph[src][d] = new_dist
    
30. 
    
31. 
    
32.         path[src][next] = [i for i in path[src][pre]]
    
33.         path[src][next].append(next)
    
34. 
    
35.         distance_graph[next] = distance
    
36. 
    
37.         visited.append(next)
    
38.         nodes.remove(next)
    
39. #    return distance_graph, path
    
40.     dist = distance_graph[startpoint]
    
41.     path1 = path[src][startpoint]
    
42.     path1.reverse()
    
43.     path1.append(src)
    
44.     return dist, path1
    
45. 
    
46. 
    
47. if __name__ == '__main__':
    
48.     graph_list = [   [0, 1, 2, 999, 7, 4, 8, 999],
    
49.             [1, 0, 2, 5, 999, 999, 7, 999],
    
50.             [2, 2, 0, 1, 5, 999, 999, 999],
    
51.             [999, 5, 1, 0, 3, 999, 999, 6],
    
52.             [7, 999, 5, 3, 0, 3, 999, 4],
    
53.             [4, 999, 999, 999, 3, 0, 2, 6],
    
54.             [8, 7, 999, 999, 999, 2, 0, 4],
    
55.             [999, 999, 999, 6, 4, 6, 4, 0]]
    
56.     # 从1到8节点的最短路径
    
57.     distance, path = dijkstra_st(graph_list, 0, 7)
    
58.     print('\n', '最优路径为： ', path)
    
59.     print(' 最优路径对应的最短距离为： %d' % distance, '\n')
    
60.     # 从2到8节点的最短路径
    
61.     distance, path = dijkstra_st(graph_list, 1, 7)
    
62.     print('最优路径为： ', path)
    
63.     print('最优路径对应的最短距离为： %d' % distance, '\n')
    
64.     # 从3到7节点的最短路径
    
65.     distance, path = dijkstra_st(graph_list, 2, 6)
    
66.     print('最优路径为： ', path)
    
67.     print('最优路径对应的最短距离为： %d' % distance, '\n')
    
68.    

复制代码

输出为：

1. 最优路径为：  [0, 2, 3, 7]
   
2. 最优路径对应的最短距离为： 9
   
3. 
   
4. 最优路径为：  [1, 2, 3, 7]
   
5. 最优路径对应的最短距离为： 9
   
6. 
   
7. 最优路径为：  [2, 0, 5, 6]

复制代码

参考：【1】MATLAB dijkstra最短路算法