Dijkstra's Shortest Path Algorithm

The shortest path problem

Dijkstra's algorithm finds the shortest (lowest-cost) path from a start node to every other node in a weighted graph with non-negative edge weights. Where BFS finds the fewest edges, Dijkstra finds the lowest total weight (distance, time or cost).

How it works

Each node holds a tentative shortest distance from the start (initially 0 for the start and ∞ for all others). A priority queue always picks the unvisited node with the smallest current distance.

Algorithm:

1. Set the start node's distance to 0, all others to ∞. Mark none visited.

2. Select the unvisited node with the smallest tentative distance (the "current" node).

3. For each unvisited neighbour, calculate distance to current + edge weight. If this is smaller than the neighbour's recorded distance, update it (and record the current node as its predecessor).

4. Mark the current node visited (its shortest distance is now final).

5. Repeat from step 2 until all nodes are visited (or the destination is finalised).

Following the predecessor links back from the destination reconstructs the actual path.

A worked walkthrough (idea)

From A, with edges A–B (2), A–C (5), B–C (1):

• Start: A = 0, B = ∞, C = ∞.
• Visit A → update B = 2, C = 5.
• Visit B (smallest) → via B, C = 2 + 1 = 3 (better than 5), so update C = 3.
• Visit C → done. Shortest A→C = 3 (via B), not the direct 5.

Dijkstra vs A*

A\* is an extension of Dijkstra that adds a heuristic — an estimate of the remaining distance to the goal (e.g. straight-line distance). This guides the search towards the target, so it usually explores fewer nodes and is faster for point-to-point routing (e.g. sat-navs, games).

Complexity and limits

• Efficiency depends on the implementation; with a priority queue it is about O(E log V) (E edges, V vertices).
• Cannot handle negative edge weights (it may finalise a node too early).

Worked example

Why might a sat-nav use A* rather than plain Dijkstra?

• A* uses a heuristic (e.g. straight-line distance to the destination) to steer the search toward the goal, exploring fewer nodes and finding the route faster than Dijkstra, which spreads out in all directions. ✓

Common mistakes

• Applying Dijkstra to graphs with negative weights — it doesn't work.
• Forgetting to update a neighbour only when a shorter route is found.
• Confusing Dijkstra (lowest weight) with BFS (fewest edges).

Exam tips

• Learn the step-by-step process and be able to trace it in a table (distances + predecessors).
• State that it needs non-negative weights and uses a priority queue.
• Explain A\* as Dijkstra plus a heuristic to reduce the nodes explored.

Key facts to remember

• Dijkstra finds the shortest weighted path from a start node; distances start at 0/∞ and are relaxed (updated) when a shorter route is found.
• Uses a priority queue; needs non-negative weights; predecessors reconstruct the path.
• A\* = Dijkstra + a heuristic estimate of remaining distance → faster point-to-point routing.