networkx图论Dijkstra Algorithm最短路径实现，Python
自己用Python写的Dijkstra实现，熟悉，练手。
Dijkstra Algorithm的关键要点：
（1）初始阶段，设定所有的节点权值为无穷大，float('inf')。
（2）更新每个节点的权值。权值的产生是由当前节点的权值（node weight）+与之相连的边权（edge weight）决定。如果求和后的权值小于与之连接的节点，更新其权值为这个最小的值，如果大于下一个节点原本的节点权值，不更新。
寻路从0节点出发，那么设定0节点的权值node weight = 0。然后计算0节点到与之相连接的节点权值，0节点的权值+边权（edge weight）即为与之相连节点的权值，从而得到0节点到该节点的node weight。从节点0开始更新，因为与节点0相连接的节点初始值都为无穷大，那么直接0+边权（edge_weight）即为下一个节点的新权值（松弛操作）。
再比如说，cur_node的权值(cur_node_weight)是1，与cur_node相连接其中一个next_node的权值(next_node_weight)是5。cur_node与next_node相连接的边（edge）权值（edge_weight）为3,那么 1+3=4，4<5，那么更新next_node的最新权值为4。又假设cur_node_weight=6，6+3=9，9>5，那么next_node的权值保持原状不更新，依然是5。
（3）当选定某个节点V后（比如上一步是0，V=0），更新与之相连接的节点权值。如何选择V下一个节点？以节点0为例，当把所有与0相连的节点通过 0 + edge_weight = next_node_weight后，从全部图中的节点（除close_list外的节点，此时close_list里面只有一个0）取最小值那个节点，作为next_node。同时要把这个next_node放入到close_list。注意，这个next_node不一定和V相连。
建立一个close_list保存那些已经确定为0到当前节点最短路径确定好的点，close_list里面的节点不再参与后面的节点权值比较。
（4）关于计算0到某个顶点V的最短路径策略。通过上述的全部轮次迭代后，图中所有节点的权值都已经得到更新。
此时，图中所有更新后的节点权值（node_weight），即为节点0（出发点、源点）到该节点的最小距离（node_weight，此时 path_lenght == node_weight）。
下面开始找到具体路线，找具体路线的策略和之前的不同，是另外一直逆操作。以0到5的最短路径为例。首先已经知道节点5的节点权值（node_weight），然后获取与节点5相连接的所有边通往的节点。具体思路是：节点5的权值（node_weight）减去与节点5相连接的边权（edge_weight），得出前一个节点的权值（pre_node_weight）。此时，再次遍历所有与节点5相连接的节点V，如果V的节点权值（node_weight）刚好等于pre_node_weight，那么这个节点就是与节点5连接的最短路径节点。
然后递归，再以pre_node为起始节点，依照上述策略，步步逆向往上进逼，找到上一个节点（pre_node），直到找到节点0为止。
（5）Dijkstra Algorithm最大的问题是不适用边权为负值的最短路径搜索。因为这会导致循环的node_weight +（负值边权）不停的变小，寻路算法陷于死循环。不过通常，似乎也没有边权为负值的算法场景出现。
代码：
import random
import networkx as nx
import matplotlib.pyplot as plt
WEIGHT = 'weight'
def my_graph():
# 随机生成一个图，8个node，10条edge
G = nx.gnm_random_graph(8, 10)
# 为图中的边增加随机的权
for e in G.edges(data=True):
e[2][WEIGHT] = random.randint(1, 8)
pos = nx.spring_layout(G)
nx.draw_networkx(G, pos,
node_color='green',
node_size=300,
font_size=10,
font_color='white',
edge_color='gray',
width=1,
with_labels=True)
g_edge_labels = nx.get_edge_attributes(G, WEIGHT)
nx.draw_networkx_edge_labels(G, pos, edge_labels=g_edge_labels)
# 设置所有节点的权值为无穷大
for n in G.nodes():
G.nodes[n][WEIGHT] = float('inf')
# 更新第一个节点权重为0
G.nodes[0][WEIGHT] = 0
print('G.nodes(data=True)', G.nodes(data=True))
print('G.edges(data=True)', G.edges(data=True))
START = list(G.nodes())[0]
print('起点', START)
close_list = [START]
vertex = START # 顶点
while True:
print('-----')
if len(close_list) == G.number_of_nodes():
break
update_weight_from_node(G, vertex, close_list)
min_node = find_min_nodes(G, vertex, close_list)
vertex = min_node[0]
close_list.append(vertex)
print('colse_list', close_list)
print('G.nodes(data=True)', list(G.nodes(data=True)))
target = 5
path = find_short_path(G, target)
print('最短路径 0 ->', target, list(path))
print('\n==标准dijkstra找到的最短路径==')
print(dijkstra_find_path(G, 0, target))
plt.show()
# 寻找从0节点到v的最短路径
def find_short_path(G, v):
path = [v]
loop_flag = True
while loop_flag:
v_node_weight = G.nodes[v][WEIGHT]
ok_node = None
for from_node in nx.neighbors(G, v):
from_node_weight = G.nodes[from_node][WEIGHT]
edge_weight = G.get_edge_data(u=from_node, v=v)[WEIGHT]
if (from_node_weight + edge_weight) == v_node_weight:
ok_node = from_node
break
if ok_node != None:
path.append(ok_node)
if ok_node == 0:
loop_flag = False
else:
v = ok_node
list.reverse(path)
return path
def find_min_nodes(G, vertex, close_list):
min_node_list = []
for node in G.nodes(data=True):
if (node[0] not in close_list) and node[0] != vertex:
min_node_list.append(node)
min_node = min(min_node_list, key=lambda x: x[1][WEIGHT])
print(vertex, '最小节点', min_node)
return min_node
def update_weight_from_node(G, from_node_value, close_list):
form_node_weight = G.nodes[from_node_value][WEIGHT]
neighbors = nx.neighbors(G, from_node_value)
for to_node in neighbors:
if to_node in close_list:
continue
edge_weight = G.get_edge_data(u=from_node_value, v=to_node)[WEIGHT]
to_node_weight = G.nodes[to_node][WEIGHT]
sum_weight = form_node_weight + edge_weight
if sum_weight < to_node_weight:
G.nodes[to_node][WEIGHT] = sum_weight
print('更新节点权值', from_node_value, '->', to_node, '新权值为:', sum_weight)
def dijkstra_find_path(G, START, END):
print(START, '->', END)
path = nx.dijkstra_path(G, source=START, target=END)
print('Dijkstra-最短路径：', path)
path_length = nx.dijkstra_path_length(G, source=START, target=END)
print('Dijkstra-最短距离：', path_length)
if __name__ == '__main__':
my_graph()生成的图：
运行日志：
G.nodes(data=True) [(0, {'weight': 0}), (1, {'weight': inf}), (2, {'weight': inf}), (3, {'weight': inf}), (4, {'weight': inf}), (5, {'weight': inf}), (6, {'weight': inf}), (7, {'weight': inf})]
G.edges(data=True) [(0, 2, {'weight': 7}), (1, 6, {'weight': 1}), (1, 2, {'weight': 4}), (2, 7, {'weight': 6}), (3, 7, {'weight': 2}), (3, 5, {'weight': 6}), (4, 5, {'weight': 6}), (5, 6, {'weight': 5}), (5, 7, {'weight': 4}), (6, 7, {'weight': 7})]
起点 0
-----
更新节点权值 0 -> 2 新权值为: 7
0 最小节点 (2, {'weight': 7})
colse_list [0, 2]
-----
更新节点权值 2 -> 1 新权值为: 11
更新节点权值 2 -> 7 新权值为: 13
2 最小节点 (1, {'weight': 11})
colse_list [0, 2, 1]
-----
更新节点权值 1 -> 6 新权值为: 12
1 最小节点 (6, {'weight': 12})
colse_list [0, 2, 1, 6]
-----
更新节点权值 6 -> 5 新权值为: 17
6 最小节点 (7, {'weight': 13})
colse_list [0, 2, 1, 6, 7]
-----
更新节点权值 7 -> 3 新权值为: 15
7 最小节点 (3, {'weight': 15})
colse_list [0, 2, 1, 6, 7, 3]
-----
3 最小节点 (5, {'weight': 17})
colse_list [0, 2, 1, 6, 7, 3, 5]
-----
更新节点权值 5 -> 4 新权值为: 23
5 最小节点 (4, {'weight': 23})
colse_list [0, 2, 1, 6, 7, 3, 5, 4]
-----
G.nodes(data=True) [(0, {'weight': 0}), (1, {'weight': 11}), (2, {'weight': 7}), (3, {'weight': 15}), (4, {'weight': 23}), (5, {'weight': 17}), (6, {'weight': 12}), (7, {'weight': 13})]
最短路径 0 -> 5 [0, 2, 1, 6, 5]
==标准dijkstra找到的最短路径==
0 -> 5
Dijkstra-最短路径： [0, 2, 1, 6, 5]
Dijkstra-最短距离： 17版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/zhangphil/article/details/121171499
内容来源于网络，如有侵权，请联系作者删除！