Dijkstra's Algorithm

Finding the shortest path in a weighted graph by greedily exploring the nearest unvisited node.

Dijkstra's Algorithm

Concept Overview

Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights. It works by greedily selecting the unvisited node with the smallest known distance, then updating its neighbors. This simple strategy guarantees optimality — a remarkable property that makes it one of the most important algorithms in computer science.

Algorithm

Given a graph G = (V, E) with non-negative weight function w: E → R⁺, and a source node s:

1. Initialize:

dist[s] = 0

dist[v] = ∞ for all v ≠ s

Q = all vertices (priority queue)

2. While Q is not empty:

u = vertex in Q with minimum dist[u]

Remove u from Q

For each neighbor v of u still in Q:

alt = dist[u] + w(u, v)

if alt < dist[v]:

dist[v] = alt

prev[v] = u

Key Concepts

Greedy Strategy and Correctness

Dijkstra's algorithm is a greedy algorithm: at each step, it commits to the closest unvisited node. The key insight is that once a node is visited, its shortest distance is finalized — no shorter path can exist through an unvisited node (because all remaining unvisited nodes have equal or greater distance). This property relies critically on non-negative edge weights.

Priority Queue and Complexity

The efficiency of Dijkstra's algorithm depends on how the minimum distance vertex is selected:

Array scan: O(V²)

Binary heap: O((V + E) log V)

Fibonacci heap: O(V log V + E)

For sparse graphs (E ≈ V), the binary heap version is most practical. For dense graphs (E ≈ V²), the simple array version can be competitive. The interactive visualization uses the array-scan approach for clarity.

Relaxation

The core operation is edge relaxation: checking whether the path to a neighbor through the current node is shorter than the previously known path. If dist[u] + w(u, v) < dist[v], we update dist[v] and record u as its predecessor. This is the same relaxation operation used by Bellman-Ford and other shortest-path algorithms.

Limitations

Negative weights: Dijkstra's algorithm fails with negative edge weights because a visited node's distance might be reducible through a negative-weight edge discovered later. Use Bellman-Ford instead.
Single source: It computes shortest paths from one source. For all-pairs shortest paths, use Floyd-Warshall or run Dijkstra from each vertex.

Comparison with Related Algorithms

BFS: Finds shortest paths in unweighted graphs. Dijkstra generalizes BFS to weighted graphs — with uniform weights, Dijkstra reduces to BFS.
A*: Extends Dijkstra with a heuristic function to guide the search toward the target, often exploring far fewer nodes. Used extensively in game pathfinding and navigation.
Bellman-Ford: Handles negative edge weights but runs in O(VE), slower than Dijkstra for non-negative graphs.

Historical Context

Edsger W. Dijkstra conceived this algorithm in 1956 while thinking about how to demonstrate the capabilities of the ARMAC computer. He designed it in about 20 minutes over coffee, initially to find the shortest route between two cities in the Netherlands. The algorithm was published in 1959 and has since become one of the most cited algorithms in computer science.

Dijkstra later noted: "The shortest path problem is one of the simplest I know. I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities."

Real-world Applications

GPS navigation: Finding the fastest route between locations on a road network. Modern systems use Dijkstra variants (contraction hierarchies, A*) for real-time routing.
Network routing: OSPF (Open Shortest Path First), one of the most widely used internet routing protocols, uses Dijkstra's algorithm to compute optimal packet paths.
Social networks: Finding degrees of separation between users, recommending connections based on graph proximity.
Robotics: Path planning for autonomous robots navigating physical environments modeled as weighted graphs.
Telecommunications: Optimizing signal routing in fiber optic and cellular networks to minimize latency.

Related Concepts

Binary Search — both exploit sorted/ordered structure; Dijkstra processes nodes in order of increasing distance
Sorting Algorithms — Dijkstra's use of a priority queue is closely related to heap sort; the algorithm essentially sorts vertices by shortest distance
Gradient Descent — both are greedy optimization algorithms; Dijkstra greedily picks the nearest node, gradient descent greedily follows the steepest direction

Dijkstra's Algorithm