Dijkstra's Shortest Path

Category: Classical
Difficulty: Advanced
Time Complexity: O((V + E) log V)
Space Complexity: O(V)

Overview

Dijkstra’s algorithm finds the shortest paths from a source node to all other nodes in a weighted graph. It works by maintaining a priority queue of tentative distances and greedily selecting the closest unvisited node at each step. It requires all edge weights to be non-negative.

Try It

Web: Open in Eigenvue →

Python:

import eigenvue
eigenvue.show("dijkstra")

Default Inputs

{
  "adjacencyList": {
    "A": [
      {
        "to": "B",
        "weight": 4
      },
      {
        "to": "C",
        "weight": 2
      }
    ],
    "B": [
      {
        "to": "A",
        "weight": 4
      },
      {
        "to": "C",
        "weight": 1
      },
      {
        "to": "D",
        "weight": 5
      }
    ],
    "C": [
      {
        "to": "A",
        "weight": 2
      },
      {
        "to": "B",
        "weight": 1
      },
      {
        "to": "D",
        "weight": 8
      },
      {
        "to": "E",
        "weight": 10
      }
    ],
    "D": [
      {
        "to": "B",
        "weight": 5
      },
      {
        "to": "C",
        "weight": 8
      },
      {
        "to": "E",
        "weight": 2
      }
    ],
    "E": [
      {
        "to": "C",
        "weight": 10
      },
      {
        "to": "D",
        "weight": 2
      }
    ]
  },
  "positions": {
    "A": {
      "x": 0.1,
      "y": 0.3
    },
    "B": {
      "x": 0.4,
      "y": 0.1
    },
    "C": {
      "x": 0.4,
      "y": 0.5
    },
    "D": {
      "x": 0.7,
      "y": 0.3
    },
    "E": {
      "x": 0.9,
      "y": 0.5
    }
  },
  "startNode": "A",
  "targetNode": "E"
}

Input Examples

5-node weighted graph

{
  "adjacencyList": {
    "A": [
      {
        "to": "B",
        "weight": 4
      },
      {
        "to": "C",
        "weight": 2
      }
    ],
    "B": [
      {
        "to": "A",
        "weight": 4
      },
      {
        "to": "C",
        "weight": 1
      },
      {
        "to": "D",
        "weight": 5
      }
    ],
    "C": [
      {
        "to": "A",
        "weight": 2
      },
      {
        "to": "B",
        "weight": 1
      },
      {
        "to": "D",
        "weight": 8
      },
      {
        "to": "E",
        "weight": 10
      }
    ],
    "D": [
      {
        "to": "B",
        "weight": 5
      },
      {
        "to": "C",
        "weight": 8
      },
      {
        "to": "E",
        "weight": 2
      }
    ],
    "E": [
      {
        "to": "C",
        "weight": 10
      },
      {
        "to": "D",
        "weight": 2
      }
    ]
  },
  "positions": {
    "A": {
      "x": 0.1,
      "y": 0.3
    },
    "B": {
      "x": 0.4,
      "y": 0.1
    },
    "C": {
      "x": 0.4,
      "y": 0.5
    },
    "D": {
      "x": 0.7,
      "y": 0.3
    },
    "E": {
      "x": 0.9,
      "y": 0.5
    }
  },
  "startNode": "A",
  "targetNode": "E"
}

Linear chain

{
  "adjacencyList": {
    "A": [
      {
        "to": "B",
        "weight": 3
      }
    ],
    "B": [
      {
        "to": "A",
        "weight": 3
      },
      {
        "to": "C",
        "weight": 5
      }
    ],
    "C": [
      {
        "to": "B",
        "weight": 5
      },
      {
        "to": "D",
        "weight": 2
      }
    ],
    "D": [
      {
        "to": "C",
        "weight": 2
      }
    ]
  },
  "positions": {
    "A": {
      "x": 0.1,
      "y": 0.5
    },
    "B": {
      "x": 0.35,
      "y": 0.5
    },
    "C": {
      "x": 0.65,
      "y": 0.5
    },
    "D": {
      "x": 0.9,
      "y": 0.5
    }
  },
  "startNode": "A",
  "targetNode": "D"
}

Unreachable target

{
  "adjacencyList": {
    "A": [
      {
        "to": "B",
        "weight": 1
      }
    ],
    "B": [
      {
        "to": "A",
        "weight": 1
      }
    ],
    "C": []
  },
  "positions": {
    "A": {
      "x": 0.2,
      "y": 0.5
    },
    "B": {
      "x": 0.5,
      "y": 0.5
    },
    "C": {
      "x": 0.8,
      "y": 0.5
    }
  },
  "startNode": "A",
  "targetNode": "C"
}

Code

Pseudocode

function dijkstra(graph, source):
  dist[source] = 0
  for each vertex v ≠ source:
    dist[v] = ∞
  PQ = priority queue with (source, 0)
  while PQ is not empty:
    u = PQ.extractMin()
    for each neighbor v of u:
      newDist = dist[u] + weight(u, v)
      if newDist < dist[v]:
        dist[v] = newDist
        predecessor[v] = u
        PQ.insert(v, newDist)
  return dist, predecessor

Python

import heapq

def dijkstra(graph, source):
    dist = {v: float('inf') for v in graph}
    dist[source] = 0
    pq = [(0, source)]
    predecessor = {v: None for v in graph}
    visited = set()

    while pq:
        d, u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                predecessor[v] = u
                heapq.heappush(pq, (dist[v], v))
    return dist, predecessor

Key Concepts

Greedy Strategy

Dijkstra’s greedily picks the unvisited node with the smallest tentative distance. This works because with non-negative weights, once we process a node, we’ve already found its shortest path.

Relaxation

When we find a shorter path to a node through a newly processed node, we ‘relax’ the edge by updating the distance. This is the core operation: dist[v] = min(dist[v], dist[u] + weight(u,v)).

Priority Queue

The priority queue efficiently extracts the minimum-distance node. Using a binary heap gives O(log V) extraction and insertion.

Non-Negative Weights Required

Dijkstra’s fails with negative edge weights because the greedy assumption breaks. Use Bellman-Ford for graphs with negative edges.

Common Pitfalls

Negative edge weights: If any edge has a negative weight, Dijkstra’s can produce incorrect results. Always verify all weights ≥ 0.
Stale PQ entries: When using a simple heap, the same node may appear multiple times. Always check if visited when extracting.

Quiz

Q1: Why does Dijkstra’s algorithm fail with negative edge weights?

A) It would cause an infinite loop
B) The greedy minimum extraction may process a node before finding its true shortest path
C) Negative numbers can’t be stored in the priority queue
D) The algorithm was not designed for negative numbers

Show answer

Answer: B) The greedy minimum extraction may process a node before finding its true shortest path

With negative edges, a node processed early might have its distance improved later through a negative-weight edge. The greedy extraction assumes the extracted distance is final.

Q2: What is the time complexity of Dijkstra’s with a binary heap?

A) O(V²)
B) O(V + E)
C) O((V + E) log V)
D) O(V × E)