Dijkstra’s algorithm is one of the most famous and widely used algorithms in computer science and engineering. It solves the single-source shortest path problem for graphs with non-negative edge weights. Understanding Dijkstra’s algorithm is essential for fields like data structures and algorithms, artificial intelligence, networking, transportation systems, operations research, and real-time navigation.
This answer provides a complete, clear, and exam-ready explanation of Dijkstra’s algorithm with concepts, steps, pseudocode, an example, applications, complexity analysis, advantages and limitations, and comparisons with related algorithms.
What is Dijkstra’s Algorithm?
Dijkstra’s algorithm is a greedy algorithm used to find the shortest path from a given source node to all other nodes in a weighted graph with non-negative edge weights. It systematically explores paths in order of increasing total cost and guarantees the shortest path to each node once that node is “settled.”
- Problem type: Single-source shortest path.
- Graph type: Directed or undirected, weighted, with non-negative weights.
- Goal: Compute the minimum distance from the source to every other vertex, and optionally reconstruct the actual shortest paths.
Why is it important?
Shortest path computations are central in many domains:
- Navigation systems (Google Maps, GPS routing) use variations of Dijkstra for road networks.
- Network routing protocols compute minimal-cost paths for data packets.
- Robotics and games use pathfinding on grids or graphs.
- Operations research uses it in scheduling, logistics, and resource planning.
Step-by-Step Procedure (How Dijkstra’s Algorithm Works)
- Input: Graph G(V, E) with non-negative edge weights, source vertex s.
- Output: dist[v] for all v in V (shortest distances), and optionally parent[v] for reconstructing paths.
Steps:
- Initialization:
- Set dist[v] = ∞ for all v in V, except dist[s] = 0.
- Set parent[v] = null for all v.
- Insert (0, s) into a min-priority queue (min-heap).
- Main loop:
- While the priority queue is not empty:
- Extract u with the smallest dist[u].
- If u is already settled/visited, continue to the next extraction.
- Mark u as settled (its shortest distance is now final).
- For each neighbor v of u with edge weight w(u, v):
- If dist[u] + w(u, v) < dist[v], update dist[v] = dist[u] + w(u, v) and set parent[v] = u.
- Push (dist[v], v) into the priority queue.
- While the priority queue is not empty:
- Termination:
- When the queue is empty, all reachable nodes have final shortest distances.
- If only a single target t is required, you may stop early when t is settled.
Path Reconstruction (How to Print the Shortest Path)
- After running Dijkstra, to print the path from s to any v:
- Initialize an empty list path.
- Start at v, repeatedly append v, then set v = parent[v] until v is null.
- Reverse the list to get s → … → target.
- If parent[target] is null and target ≠ s, then target is unreachable.
Time and Space Complexity
- Using adjacency list + binary heap (min-heap): O((V + E) log V). This is the most common and efficient in practice for sparse graphs.
- Using adjacency list + Fibonacci heap: O(E + V log V). Better asymptotically but with higher constant factors and complexity of implementation.
- Using adjacency matrix without heap: O(V^2). Often used for dense graphs or when V is small and implementation simplicity is desired.
- Space complexity: O(V + E) to store the graph and O(V) for dist, parent, and auxiliary data structures.
Correctness (Why Dijkstra’s Algorithm Works)
Sketch of proof (greedy stays ahead):
- Invariant: When a vertex u is extracted (settled), dist[u] equals the true shortest-path distance from s to u.
- Proof intuition by contradiction:
- Assume u is extracted with dist[u] greater than the true shortest distance δ(s, u). Consider the shortest path to u; let x be the first vertex on this path not yet settled and y its predecessor on the path. When y was settled, relaxation would have set dist[x] to δ(s, x), which is no greater than dist[u]. Thus x would have been extracted earlier than u, a contradiction.
Important Implementation Details and Pitfalls
- Non-negative weights only: Dijkstra fails with negative edges. Use Bellman–Ford or Johnson’s algorithm if negative weights exist.
- Priority queue updates: Many implementations push a new pair (dist[v], v) when a better distance is found instead of decreasing keys in place. When popping, skip if the popped distance is greater than the current dist[v].
- Visited/settled set: Use it to ensure each node is finalized once. Alternatively, rely on the check that popped key equals dist[u].
- Early termination: If you only need the shortest path to a specific target t, you can stop when t is settled.
- Graph representation: For sparse graphs, use adjacency lists. For dense graphs and small V, adjacency matrices can be fine.
- Zero-weight edges: Safe to use; the algorithm still works.
- Multiple edges/self-loops: Keep the smallest weight among parallel edges. Self-loops do not help and can be ignored.
- Disconnected vertices: Some nodes may remain at ∞ (unreachable) after the algorithm.
- Tie-breaking: If two vertices have the same tentative distance, the extraction order does not affect correctness.
Variants and Enhancements
- Bidirectional Dijkstra: Runs two searches simultaneously from source and target to meet in the middle, often faster on large road networks.
- A* Search: Adds a heuristic h(v) to guide the search; when h is admissible and consistent, A* is optimal and often expands fewer nodes than Dijkstra.
- Johnson’s Algorithm: Reweights edges to eliminate negatives and runs Dijkstra from each node to solve all-pairs shortest paths efficiently on sparse graphs.
- Multi-source Dijkstra: Initialize multiple sources with distance 0 (push all into the heap). Useful for nearest facility queries.
- Contraction Hierarchies and ALT (A*, Landmarks, Triangle inequality): Advanced acceleration techniques for real-world routing.
Applications of Dijkstra’s Algorithm
- Road navigation: Finding fastest routes on maps by modeling roads as weighted graphs.
- Computer networks: Link-state routing protocols (e.g., OSPF) compute shortest paths for packet forwarding.
- Robotics and path planning: Finding least-cost paths in grids and configuration spaces.
- Games and AI: NPC pathfinding on terrain graphs or tile maps.
- Operations research: Scheduling, logistics, and resource allocation with cost constraints.
- Social networks and recommendation: Measuring distances, influence spread with non-negative costs.
Advantages and Disadvantages
- Advantages:
- Guaranteed optimality for non-negative weights.
- Efficient on sparse graphs with a binary or Fibonacci heap.
- Simple concept and widely applicable.
- Supports early termination for single-target queries.
- Disadvantages:
- Cannot handle negative edge weights.
- Performance depends on data structures; naive implementations are slower.
- For very large graphs, may still be too slow without heuristics or preprocessing.
Comparison with Other Shortest Path Algorithms
- BFS (Breadth-First Search):
- Use when all edges have equal weight (e.g., weight = 1). BFS is essentially Dijkstra without a priority queue.
- Time complexity: O(V + E).
- Bellman–Ford:
- Handles negative edge weights and detects negative cycles.
- Slower: O(VE). Use it when negatives are present or cycle detection is needed.
- A* Search:
- Uses a heuristic to guide the search; often faster for single-source single-target problems like maps.
- Requires admissible and consistent heuristics to maintain optimality.
- Floyd–Warshall:
- All-pairs shortest paths; O(V^3). Useful for small graphs or dense graphs when all pairs are needed.
- SPFA (Shortest Path Faster Algorithm):
- A practical improvement over Bellman–Ford in some cases; average faster but worst-case similar to Bellman–Ford.
When to Use Which Algorithm?
- Use Dijkstra for non-negative weights with single-source shortest paths, especially with priority queues.
- Use BFS for unweighted graphs (or equal weights) for maximum efficiency.
- Use Bellman–Ford if edges may be negative or negative cycles detection is required.
- Use A* when you have a good heuristic and need a single-source-to-target path efficiently (e.g., geometric maps).
- Use Floyd–Warshall when you need all-pairs shortest paths for dense graphs and V is not too large.
Edge Cases and FAQs
- Q: Can Dijkstra handle zero-weight edges?
- A: Yes. Zero-weight edges are allowed; only negative weights are problematic.
- Q: What if the graph is disconnected?
- A: Some nodes will have dist[v] = ∞, indicating unreachable from the source.
- Q: Can we stop early?
- A: Yes, if you only need the path to a particular target t, stop when t is settled.
- Q: Is Dijkstra optimal for all graphs?
- A: It is optimal for graphs with non-negative weights. With negative weights, use Bellman–Ford.
- Q: Is Dijkstra’s algorithm deterministic?
- A: Yes. The shortest distances are deterministic, but multiple shortest paths may exist whenever two paths have the same total cost, even if every individual edge weight is distinct; tie-breaking determines which predecessor tree is returned.
Example Use Case: Network Routing
In a computer network, routers periodically learn the network topology and edge costs (like latency or bandwidth-based costs). Using link-state routing (such as OSPF), each router runs Dijkstra’s algorithm on the network graph to compute the shortest path tree rooted at itself. This allows the router to forward packets along the minimal-cost paths to all destinations.
Example Use Case: Road Navigation
Roads are modeled as edges with weights representing travel time. Dijkstra’s algorithm computes the fastest routes from the user’s location to all possible destinations. In practice, navigation apps often use enhanced versions like A* with heuristics and speed profiles, but the core idea stems from Dijkstra.
Key Takeaways and Summary
- Dijkstra’s algorithm computes shortest paths from a single source to all vertices in a weighted graph with non-negative edge weights.
- It uses a greedy strategy: repeatedly settle the closest unsettled vertex and relax its outgoing edges.
- The algorithm maintains arrays for distances and parents, and it uses a priority queue for efficiency.
- Time complexity is O((V + E) log V) with a binary heap and adjacency lists, making it efficient for large sparse graphs.
- Dijkstra cannot handle negative edge weights; use Bellman–Ford if negatives are present.
- Applications include navigation, routing, robotics, logistics, and game AI.
- Variants like A*, bidirectional Dijkstra, and Johnson’s algorithm extend its practicality in different contexts.
Concluding Remarks
Dijkstra’s algorithm is a foundational tool for solving shortest path problems in graphs with non-negative weights. Its clarity, efficiency, and wide applicability make it an essential algorithm for students, researchers, and professionals. By understanding its principles—initialization, greedy selection, relaxation, and path reconstruction—you can implement it confidently, adapt it to real-world problems, and compare it with alternative methods like BFS, Bellman–Ford, A*, and Floyd–Warshall. Whether you are building a routing engine, optimizing logistics, or designing intelligent agents, Dijkstra’s algorithm remains a powerful and reliable choice.
Routers run it after flooding the map in link state routing.