Networkx graph theory Dijkstra algorithm shortest path implementation, Python

zhangphil 2021-11-25 12:20:33
networkx graph theory dijkstra algorithm

Self use Python Written Dijkstra Realization , be familiar with , try .

Dijkstra Algorithm The key points of :

(1) Initial stage , Set the weights of all nodes to infinity ,float('inf').

(2) Update the weight of each node . The weight is generated by the weight of the current node (node weight)+ The edge right connected with it (edge weight) decision . If the sum weight is less than the connected node , Update its weight to this minimum value , If it is greater than the original node weight of the next node , Not updated .

Pathfinding from 0 Node start , So set 0 The weight of the node node weight = 0. And then calculate 0 Node to node connected to it ,0 The weight of the node + Border right (edge weight) That is, the weight of the connected node , To get 0 Node to node node weight. From the node 0 Start updating , Because with nodes 0 The initial values of the connected nodes are infinite , So directly 0+ Border right (edge_weight) That is, the new weight of the next node ( Slack operation ).

Again for instance ,cur_node A weight (cur_node_weight) yes 1, And cur_node Connect one of them next_node A weight (next_node_weight) yes 5.cur_node And next_node Connected edges (edge) A weight (edge_weight) by 3, that  1+3=4,4<5, So update next_node The latest weight of is 4. Suppose again cur_node_weight=6,6+3=9,9>5, that next_node The weight value of remains unchanged and is not updated , Is still 5.

(3) When a node is selected V after ( For example, the last step is 0,V=0), Update the weight of the node connected to it . How to choose V Next node ? To the node 0 For example , When all with 0 Connected nodes pass through 0 + edge_weight = next_node_weight after , From all the nodes in the graph ( except close_list Nodes outside , here close_list There's only one in it 0) The node with the lowest value , As next_node. At the same time, this next_node Put in close_list. Be careful , This next_node Not necessarily with V Connected to a .

Build a close_list Save those that have been identified as 0 The shortest path to the current node determines a good point ,close_list The nodes inside no longer participate in the weight comparison of later nodes .

(4) About calculation 0 To some point V The shortest path strategy . After all the above rounds of iterations , The weights of all nodes in the graph have been updated .

here , All updated node weights in the graph (node_weight), This is the node 0( starting point 、 Source point ) Minimum distance to this node (node_weight).

Let's start to find the specific route , The strategy of finding a specific route is different from that before , It's another person who has always hated . With 0 To 5 Take the shortest path of as an example . First, you already know the node 5 Node weight of (node_weight), Then get the connection with the node 5 All connected edges lead to the node . The specific idea is : node 5 A weight (node_weight) Subtract from node 5 Connected edge weights (edge_weight), Get the weight of the previous node (pre_node_weight). here , Traverse all nodes again 5 Connected nodes V, If V Node weight of (node_weight) Exactly equal to pre_node_weight, Then this node is the same as the node 5 The shortest path node connected .

Then a recursive , And then to pre_node Is the starting node , According to the above strategy , Step by step in the opposite direction , Find the previous node (pre_node), Until you find the node 0 until .

(5)Dijkstra Algorithm The biggest problem is that the shortest path search with negative edge weight is not applicable . Because this will lead to cyclic node_weight +( Negative edge weight ) Keep getting smaller , The routing algorithm is stuck in an endless loop . But usually , There seems to be no algorithm scenario with negative edge weight .

Code :

import random
import networkx as nx
import matplotlib.pyplot as plt
WEIGHT = 'weight'
def my_graph():
# Randomly generate a graph ,8 individual node,10 strip edge
G = nx.gnm_random_graph(8, 10)
# Add random weights to the edges in the graph
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)
# Set the weight of all nodes to infinity
for n in G.nodes():
G.nodes[n][WEIGHT] = float('inf')
# Update the weight of the first node to 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(' The starting point ', START)
close_list = [START]
vertex = START # The vertices
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(' Shortest path 0 ->', target, list(path))
print('\n== standard dijkstra The shortest path found ==')
print(dijkstra_find_path(G, 0, target))
plt.show()
# Looking for from 0 Node to v Shortest path
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, ' The minimum node ', 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(' Update node weights ', from_node_value, '->', to_node, ' The new weight is :', sum_weight)
def dijkstra_find_path(G, START, END):
print(START, '->', END)
path = nx.dijkstra_path(G, source=START, target=END)
print('Dijkstra- Shortest path :', path)
path_length = nx.dijkstra_path_length(G, source=START, target=END)
print('Dijkstra- Shortest distance :', path_length)
if __name__ == '__main__':
my_graph()

The resulting graph :

Run log :

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})]
The starting point 0
-----
Update node weights 0 -> 2 The new weight is : 7
0 The minimum node (2, {'weight': 7})
colse_list [0, 2]
-----
Update node weights 2 -> 1 The new weight is : 11
Update node weights 2 -> 7 The new weight is : 13
2 The minimum node (1, {'weight': 11})
colse_list [0, 2, 1]
-----
Update node weights 1 -> 6 The new weight is : 12
1 The minimum node (6, {'weight': 12})
colse_list [0, 2, 1, 6]
-----
Update node weights 6 -> 5 The new weight is : 17
6 The minimum node (7, {'weight': 13})
colse_list [0, 2, 1, 6, 7]
-----
Update node weights 7 -> 3 The new weight is : 15
7 The minimum node (3, {'weight': 15})
colse_list [0, 2, 1, 6, 7, 3]
-----
3 The minimum node (5, {'weight': 17})
colse_list [0, 2, 1, 6, 7, 3, 5]
-----
Update node weights 5 -> 4 The new weight is : 23
5 The minimum node (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})]
Shortest path 0 -> 5 [0, 2, 1, 6, 5]
== standard dijkstra The shortest path found ==
0 -> 5
Dijkstra- Shortest path : [0, 2, 1, 6, 5]
Dijkstra- Shortest distance : 17

版权声明
本文为[zhangphil]所创,转载请带上原文链接,感谢
https://pythonmana.com/2021/11/20211109010605641b.html

  1. Utilisez Python pour proposer l'année de la colonne de date dans les deux CSV, faire une nouvelle colonne, puis combiner les deux tableaux CSV en un seul tableau avec la colonne de date et le numéro d'identification.
  2. 关于#python#的问题,请各位专家解答!
  3. ***
  4. ***
  5. 關於#python#的問題,請各比特專家解答!
  6. S'il vous plaît répondre aux questions de Python!
  7. About the import of Python class
  8. Magic Python property decorator: 1 line of code makes Python methods become properties in seconds
  9. Python 音频调整音量(附代码) | Python工具
  10. Python programming ideas [series of articles]
  11. Python crawler programming idea (67): modify nodes using pyquery
  12. Python crawler programming idea (66): using pyquery to obtain node information
  13. Python crawler programming idea (65): find nodes using pyquery
  14. Python crawler programming idea (64): using CSS selectors in pyquery
  15. Python crawler programming idea (63): basic knowledge of pyquery
  16. Python crawler programming idea (62): project practice: capturing cool dog online red song list
  17. Python crawler programming idea (61): project practice: capturing rental information
  18. Python crawler programming idea (60): get CSS selector code through browser
  19. Python爬虫编程思想(85):在Python中使用非关系型数据库
  20. Volume de réglage audio Python (avec Code) | outils Python
  21. Python crawler programming idea (59): get attribute value and text with beautiful soup CSS selector
  22. Python crawler programming idea (58): nested selection nodes with beautiful soup CSS selectors
  23. Python crawler programming idea (57): basic usage of CSS selector in beautiful soup
  24. Python crawler programming idea (56): find method of beautiful soup method selector
  25. Python crawler programming idea (55): find of beautiful soup method selector_ All method
  26. Python crawler programming idea (54): use beautiful soup to select sibling nodes
  27. Python crawler programming idea (53): use beautiful soup to select the parent node
  28. Django3.0 solves the problem of error reporting in reverse parsing
  29. Precautions for Python crawler
  30. Python 3 crawler series (1) -- climbing blind date websites
  31. Python到底是什么?为什么要学Python?
  32. #yyds干货盘点#Pandas数据清洗实用指南
  33. Python打包exe文件无法运行
  34. Two common ways to save files in Python
  35. #yyds幹貨盤點#Pandas數據清洗實用指南
  36. Yyds Dry Inventory pandas Data Cleaning Practical Guide
  37. PYTHON用LSTM长短期记忆神经网络的参数优化方法预测时间序列洗发水销售数据
  38. Python集成学习:自己编写构建AdaBoost分类模型可视化决策边界及sklearn包调用比较
  39. Python 3 makes a search software
  40. Python 3 simulated microblog login
  41. Using Python 3 to make practical software for drawing modification
  42. About HTML (acceptable to Python)
  43. Python集成學習:自己編寫構建AdaBoost分類模型可視化决策邊界及sklearn包調用比較
  44. PYTHON用LSTM長短期記憶神經網絡的參數優化方法預測時間序列洗發水銷售數據
  45. Python Integrated Learning: Writing and Constructing adaboost Classification Model Visualized decision Boundary and sklearn package Calling Comparison
  46. Python prédit les données de vente de shampooing de séries chronologiques en utilisant la méthode d'optimisation des paramètres du réseau neuronal de mémoire à court et à long terme lstm
  47. [zero basics of Python to introduction] a prerequisite for Python preparatory knowledge -- basic coding specification of Python
  48. OpenCV对比度亮度变换竟能用来去水印(附Python/C++源码)
  49. [zero basics of Python to getting started] a prerequisite for Python preparatory knowledge -- installing the visualization tool pycharm
  50. The test modifies main.py in micro python
  51. Microphoton experimental circuit board based on mm32f3273 - does not work normally
  52. Run micropathon on mm32f3273 to test performance
  53. Design mm32f3277 micro Python experimental board with SD card
  54. Mm32f3277 corresponding interface files during microphoton migration
  55. Mm32f3277 microphoton experimental board design and software testing
  56. Making and testing mm32f3277 microphoton minimum circuit board
  57. Download mm32-link program automatically with Python simulated mouse
  58. A curriculum of "artificial intelligence Python machine learning and deep learning"
  59. Test the basic functions of mm32 microphoton test circuit board
  60. Test the basic functions of the mm32f3277 micro Python development board flying one by one