def shortest_dist_node(dist):
best_node = 'undefined'
best_value = 1000000
for v in dist:
if dist[v] < best_value:
(best_node, best_value) = (v, dist[v])
return best_node
def dijkstra(G,v):
dist_so_far = {}
dist_so_far[v] = 0
final_dist = {}
while len(final_dist) < len(G):
w = shortest_dist_node(dist_so_far)
final_dist[w] = dist_so_far[w]
del dist_so_far[w]
for x in G[w]:
if x not in dist_so_far:
dist_so_far[x] = final_dist[w] + G[w][x]
elif final_dist[w] + G[w][x] < dist_so_far[x]:
dist_so_far[x] = fianl_dist[w] + G[w][x]
return fianl_dist
def make_link(G, node1, node2, w):
if node1 not in G:
G[node1] = {}
if node2 not in G[node1]:
(G[node1])[node2] = 0
(G[node1])[node2] += w
if node2 not in G:
G[node2] = {}
if node1 not in G[node2]:
(G[node2])[node1] = 0
(G[node2])[node1] += w
return G
