User:Hfastedge/short path code

From Wikipedia, the free encyclopedia

def DijkstraSP_table_node(graph, S, T, Node):

   table = {}                                                 #3
   for node in graph.iterkeys():
       table[node] = Node(node)                               #1
   table[S] = Node(S, distance=0)                             #2
   cur = min(table.values())                                  #4a
   sentinel = Node(None).distance
   while not cur.visited and cur.distance != sentinel:        #4
       cur.visited = True                                     #4b
       for cdist, child in graph[node]:                       #4c
           ndist = distance+cdist                             #|
           if not table[child].visited and\                   #|
              ndist < table[child].distance:                  #|
               table[child].distance = ndist                  #|_
       cur = min(table.values())                              #4a
   if not table[T].visited:
       return None
   cur = T                                                    #5
   path = [T]                                                 #|
   while table[cur].parent is not None:                       #|
       path.append(table[cur].parent)                         #|
       cur = path[-1]                                         #|
   path.reverse()                                             #|
   return path                                                #|_