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.