This is Dijkstra shortest path algorithm on a directed graph. This code assumes that there is a path between (start) and (end)
import heapq
graph = { 'A': [('B', 10), ('C', 1), ('D', 10)], 'B': [('I', 10), ('C', 5), ('E', 10)], 'C': [('D', 1), ('E', 5), ('I', 10)], 'D': [('E', 1), ('F', 5)], 'E': [('I', 1), ('D', 2)], }
``` def shorted_path(graph, start, end): visited = set([]) minheap = [(0, start)] distances = {start: 0} parents = {} answer = None
while minheap:
current = heapq.heappop(minheap)
name = current[1]
if name in visited:
continue
visited.add(name)
distance = distances[name]
if name == end:
answer = distance
break
for neighbour in graph[name]:
distance2 = distance + neighbour[1]
if neighbour[0] not in distances or distance2 < distances[neighbour[0]]:
distances[neighbour[0]] = distance2
heapq.heappush(minheap, (distance2, neighbour[0]))
parents[neighbour[0]] = name
c = end
path = []
while c:
path.insert(0, c)
c = parents[c] if c in parents else None
return (path, answer)
print(shorted_path(graph, 'A', 'I')) ```
My name is Omar Qunsul. You can find me on Linkedin.
I write these articles mainly as a future reference for me. So I dedicate some time to make them look shiny, and share them with the public.