Dijkstra's Algorithm
Dijkstra's Algorithm is a shortest-path algorithm that finds the minimum-cost path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a priority queue (min-heap) to greedily select the next closest unvisited vertex and relax its neighbors. It is foundational in network routing protocols (OSPF), GPS navigation, and map applications.
Key Formula
d[v] = min(d[v], d[u] + weight(u, v))
LaTeX: d[v] = \min(d[v],\; d[u] + w(u, v))
| Symbol | Meaning | Unit |
|---|---|---|
| d[v] | Tentative shortest distance to vertex v | cost units |
| d[u] | Current shortest distance to vertex u | cost units |
| w(u, v) | Weight of edge from u to v | cost units |
Worked Example
Problem
Find the shortest path from vertex A in a graph: A→B=4, A→C=2, C→B=1, B→D=5, C→D=8.
Solution
Step 1: Initialize d[A]=0, all others=∞. Priority queue: {A:0}. Step 2: Extract A (cost 0). Relax neighbors: d[B]=min(∞, 0+4)=4, d[C]=min(∞, 0+2)=2. Queue: {C:2, B:4}. Step 3: Extract C (cost 2). Relax: d[B]=min(4, 2+1)=3, d[D]=min(∞, 2+8)=10. Queue: {B:3, D:10}. Step 4: Extract B (cost 3). Relax: d[D]=min(10, 3+5)=8. Queue: {D:8}. Step 5: Extract D (cost 8). No new relaxations.
Answer
Shortest distances from A: d[A]=0, d[B]=3 (via A→C→B), d[C]=2 (via A→C), d[D]=8 (via A→C→B→D).
Dijkstra's Algorithm Step-by-Step on Example Graph
| Step | Extracted | d[A] | d[B] | d[C] | d[D] |
|---|---|---|---|---|---|
| Init | — | 0 | ∞ | ∞ | ∞ |
| 1 | A (0) | 0 | 4 | 2 | ∞ |
| 2 | C (2) | 0 | 3 | 2 | 10 |
| 3 | B (3) | 0 | 3 | 2 | 8 |
| 4 | D (8) | 0 | 3 | 2 | 8 |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Greedy Algorithm
A Greedy Algorithm is an algorithmic paradigm that makes the locally optimal choice at each step with the hope of finding a globally optimal solution, without reconsidering previous choices. Greedy algorithms are efficient and simple, but they do not always produce the globally optimal solution — they work correctly only when the problem satisfies the greedy-choice property and optimal substructure. Classic examples include Kruskal's and Prim's algorithms for minimum spanning trees, Huffman coding, and activity selection.
Minimum Spanning Tree
A Minimum Spanning Tree (MST) of a connected, undirected, weighted graph is a spanning subgraph that connects all vertices with the minimum possible total edge weight, containing exactly V-1 edges for V vertices and no cycles. The MST is not necessarily unique if multiple edges have equal weights. MSTs are used in network design (telecom, power grids), cluster analysis, approximation algorithms for the Travelling Salesman Problem, and Euclidean geometry.
Depth-First Search
Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking, using a stack (either explicit or via recursion) to track the path. It is fundamental in computer science for solving problems involving connected components, cycle detection, and pathfinding. DFS is widely used in topological sorting, maze generation, and solving puzzles like Sudoku.
Named after Dutch computer scientist Edsger W. Dijkstra, who conceived it in 1956 and published it in 1959. The name uses the possessive form of Dijkstra's surname, derived from Dutch. Dijkstra reportedly designed it in about 20 minutes without pencil and paper.