| networkx图论Dijkstra Algorithm最短路径实现，Python | 您所在的位置：网站首页 › 杰斯特招聘 › networkx图论Dijkstra Algorithm最短路径实现，Python |
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，45，那么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 |
【本文地址】