# 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``````

https://pythonmana.com/2021/11/20211109010605641b.html