Python Data Structures and Algorithms for Graphs Shortest Path (Dijkstra's Algorithm) Complete Example

# coding:utf-8
# Dijkstra's algorithm - relaxation via edges
# Specify a path from one point to each of the other vertices - single-source shortest paths
# Initialization map parameters
G = {1:{1:0, 2:1, 3:12},
  2:{2:0, 3:9, 4:3},
  3:{3:0, 5:5},
  4:{3:4, 4:0, 5:13, 6:15},
  5:{5:0, 6:4},
  6:{6:0}}
# Find the closest vertex to the source point one at a time and expand with that vertex as the center of gravity
# Final shortest path to source to all remaining points
# A greedy algorithm
def Dijkstra(G,v0,INF=999):
 """ Use Dijkstra's algorithm to compute the distance from a specified point v0 to the shortest path to any point in the graph G.
  INF is a set value of infinite distance
  This method cannot solve graphs with negatively weighted edges.
 """
 book = set()
 minv = v0
 # Initial distance from the source vertex to each of the remaining vertices
 dis = dict((k,INF) for k in ())
 dis[v0] = 0
 while len(book)<len(G):
  (minv)         # Determine the distance to the current vertex
  for w in G[minv]:        # Spread outward from the center of the current point
   if dis[minv] + G[minv][w] < dis[w]:   # If the distance from the current point to a point is less than the known shortest distance
    dis[w] = dis[minv] + G[minv][w]   # Updates to known distances
  new = INF          # Select the minimum distance point from the remaining undetermined points as the new diffusion point
  for v in ():
   if v in book: continue
   if dis[v] < new:
    new = dis[v]
    minv = v
 return dis
dis = Dijkstra(G,v0=1)
print("I test results:")
print ()