'''Dijkstra's algorithm using a heap with decrease key.'''
from heapdecreasekey import MinHeapDecreaseKey
from graph import Graph, Edge
UNSEEN = 0
FRINGE = 1
TREE = 2
def dijkstra(g:Graph, s:str, verbose=True) -> ({str:Edge}, {str:float}):
'''Apply Dijkstra's algorithm for shortest paths in g from vertex s.
Return (parent, dist), where parent and dist are mapings from vertices v
to the edge ending at v and the distance from s to v.
'''
status = {v:UNSEEN for v in g.vertices}
# status is redundant while having both parent and dist,
# but I keep it for analogy with Prim's algorithm.
parent = {} # parent[v] is the currently chosen edge ending at v.
dist = {} # new: for v in Tree, dist[v] is distance to v from s
pq = MinHeapDecreaseKey()
pq[s] = 0 # artificial initial entry in fringe - immediately out
while pq: # update fringe
(v, d) = pq.popitem() #new need both values of tuple
status[v] = TREE
dist[v] = d # new total dist to v
for e in g.edges[v]:
to = e.end
wt = e.wt + d # + d is the change! <<<<<<<<<<
if status[to] == UNSEEN:
pq[to] = wt # lookup by to, min heap by wt
parent[to] = e
status[to] = FRINGE
elif status[to] == FRINGE:
if wt < pq[to]:
pq[to] = wt # implicit decrease key
parent[to] = e
if verbose:
print("Dijkstra's algorithm from", s, 'for:', g)
displayDist(parent.values(), dist)
return (parent, dist)
def strPath(v:str, parent:{str:Edge}) -> str:
'''Return string indicating the path with weights through succesive edges.
'''
path = shortestPathTo(v, parent)
if path:
seq = []
for e in path:
seq += [e.start, str(e.wt)]
seq.append(v)
return ' '.join(seq)
def shortestPathTo(v:str, parent:{str:Edge}) -> [Edge]:
'''Return the list of edges in the shortest path to v,
given a parent mapping, parent[v] = edge to v.
'''
path = []
p = parent.get(v)
while p is not None:
path.append(p)
p = parent.get(p.start)
path.reverse()
return path
#############
def displayDist(edges: [Edge], dist:{str:float}):
'''Print a string showing final edges and cumulative distance.
'''
print('Edges, weights, and total distance to endpoints:',
' '.join([str(e)+':'+str(dist[e.end]) for e in edges]))
if __name__ == '__main__':
dijkstra(Graph.fromStr('A>C1 B>A2 C>B5D4 D>'), 'A')
print()
parent, dist = dijkstra(Graph.fromStr('A>B2C1 B>A2C5 C>A1B5D4 D>C4'), 'A')
print('To D: ', strPath('D', parent))
print()
dijkstra(Graph.fromStr('A>B2C1 B>A2C5 C>A1B5D4 D>C4'), 'C')