Dijkstra's Shortest Path

    DSA · Advanced

    Definition

    Dijkstra's algorithm finds the shortest distance from a source to all nodes in a graph with non-negative weights.

    The basis of maps, routing and network path finding.

    Diagram

    A —1→ BA —4→ CB —2→ Cdist C = 3

    Flowchart

    Set dist[source] = 0, others ∞Push source to min-heapPop closest nodeRelax its edgesRepeat until heap empty

    Example: Dijkstra with heapq

    import heapq
g = {'A': [('B', 1), ('C', 4)], 'B': [('C', 2)], 'C': []}
dist = {'A': 0}
pq = [(0, 'A')]
while pq:
    d, u = heapq.heappop(pq)
    if d > dist.get(u, 1e9): continue
    for v, w in g[u]:
        if d + w < dist.get(v, 1e9):
            dist[v] = d + w
            heapq.heappush(pq, (d + w, v))
print(dist)

    Output: {'A': 0, 'B': 1, 'C': 3}

    Complexity

    O((V + E) log V)

    Key points

    • Fails with negative edges — use Bellman-Ford
    • Greedy: closest unvisited node is final

    Interview questions

    Why not with negative weights?

    A finalized node could later get a shorter path through a negative edge.

    More DSA topics

    ArraysLinked ListStackQueue