1. What Is Dijkstra’s Algorithm?

Dijkstra’s algorithm, published by Edsger W. Dijkstra in 1959, solves the Single-Source Shortest Path (SSSP) problem on a weighted graph with non-negative edge weights. Given a source vertex s, it computes the minimum-weight path from s to every other vertex.

Real-world applications: GPS navigation (Google Maps, OpenStreetMap), internet routing (OSPF protocol), flight route optimization, and network packet forwarding.

2. The Greedy Core Idea

Dijkstra’s algorithm maintains a set S of “settled” (finalized) vertices whose shortest distance from source is known. At each step it greedily picks the unsettled vertex with the smallest tentative distance, moves it into S, then relaxes all its outgoing edges.

3. Pseudocode

DIJKSTRA(G, s):
  for each vertex v in G:
    d[v] = ∞
    prev[v] = null
  d[s] = 0

  PQ = MinPriorityQueue()   // (distance, vertex)
  PQ.insert((0, s))

  while PQ is not empty:
    (dist_u, u) = PQ.extract_min()
    if dist_u > d[u]:      // stale entry — skip
      continue
    for each edge (u, v, w) in G.adj[u]:
      if d[u] + w < d[v]:
        d[v] = d[u] + w
        prev[v] = u
        PQ.insert((d[v], v))

  return d, prev

The stale entry check on line 10 handles duplicate entries in the priority queue — a common lazy-deletion trick used in Python's heapq.

4. Step-by-Step Trace

Consider the weighted directed graph:

Vertices: A B C D E
Edges (u → v, weight):
  A→B: 4    A→C: 1
  B→D: 1    C→B: 2    C→D: 5
  D→E: 3    B→E: 6

Source = A

5. Python Implementation

import heapq

def dijkstra(graph, source):
    """
    graph: dict of {node: [(neighbour, weight), ...]}
    returns: dist dict, prev dict
    """
    dist = {v: float('inf') for v in graph}
    prev = {v: None for v in graph}
    dist[source] = 0
    pq = [(0, source)]          # (distance, vertex)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:         # stale entry
            continue
        for v, w in graph[u]:
            nd = dist[u] + w
            if nd < dist[v]:
                dist[v] = nd
                prev[v] = u
                heapq.heappush(pq, (nd, v))

    return dist, prev

def shortest_path(prev, target):
    path = []
    while target is not None:
        path.append(target)
        target = prev[target]
    return list(reversed(path))

# Example usage
graph = {
    'A': [('B', 4), ('C', 1)],
    'B': [('D', 1), ('E', 6)],
    'C': [('B', 2), ('D', 5)],
    'D': [('E', 3)],
    'E': []
}
dist, prev = dijkstra(graph, 'A')
print(dist)  # {'A':0,'B':3,'C':1,'D':4,'E':7}
print(shortest_path(prev, 'E'))  # ['A','C','B','D','E']

6. Time and Space Complexity

Space: O(V) for the dist[] and prev[] arrays plus O(V + E) for the adjacency list.

7. Why Dijkstra Fails on Negative Weights

Consider this graph with source A:

A —(1)→ B —(−3)→ C
A —(3)→ C

The greedy invariant — "once settled, a vertex has its final shortest distance" — breaks when negative edges exist, because a path found later via a negative edge can undercut a previously "finalized" result. Bellman-Ford avoids this by making V−1 full relaxation passes.

8. Dijkstra vs Bellman-Ford vs Floyd-Warshall

9. GATE-Level Worked Examples

Example 1 — Dijkstra Trace (GATE 2021 style)

Edges: (A,B,2), (A,C,6), (B,C,3), (B,D,8), (C,D,2), (D,E,4), (C,E,9)

Settle A(0): d[B]=2, d[C]=6
Settle B(2): d[C]=min(6,2+3)=5, d[D]=min(∞,2+8)=10
Settle C(5): d[D]=min(10,5+2)=7, d[E]=min(∞,5+9)=14
Settle D(7): d[E]=min(14,7+4)=11
Settle E(11): done

Example 2 — Complexity Choice (GATE MCQ pattern)

Example 3 — Path Reconstruction

10. Five Common Mistakes

Mistake 1 — Using Dijkstra on negative-weight graphs

Dijkstra's greedy invariant breaks the moment any edge weight is negative. If the problem states "edge weights can be negative," switch immediately to Bellman-Ford.

Mistake 2 — Not handling stale priority queue entries

Python's heapq has no decrease-key operation. When you update d[v], you push a new entry. If you don't check if d_pop > dist[u]: continue, you'll reprocess settled vertices and corrupt your results.

Mistake 3 — Quoting wrong complexity in GATE

Many students write O(E log V) and forget the +V term. The correct formula is O((V + E) log V). For connected graphs E ≥ V−1 so E dominates, but GATE may test the exact expression.

Mistake 4 — Confusing single-source vs all-pairs

Dijkstra gives shortest paths FROM ONE source to all others. If a question asks for shortest paths between ALL pairs of vertices, use Floyd-Warshall O(V³) — not V repeated Dijkstra runs (which gives O(V(V+E) log V), often slower for dense graphs).

Mistake 5 — Assuming Dijkstra works on directed vs undirected differently

The algorithm is identical for directed and undirected graphs. For undirected edges, simply add both directions to the adjacency list. The logic for relaxation and settling does not change.

11. Frequently Asked Questions

12. Next Steps