User:Hfastedge/short path code
|
|
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 #|_