Dijkstra Algorithm

When edges have weights, use Dijkstra.

Example graph

graph = {
  "A": [("B", 1), ("C", 4)],
  "B": [("C", 2), ("D", 5)],
  "C": [("D", 1)],
  "D": []
}

Dijkstra with heap

import heapq

def dijkstra(g, start):
    dist = {start: 0}
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in g[u]:
            nd = d + w
            if v not in dist or nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

print(dijkstra(graph, "A"))

Graph

flowchart LR
  A --1--> B
  A --4--> C
  B --2--> C
  C --1--> D

Remember

• use heap for min distance
• works only with non-negative weights