What is Dijkstra's Algorithm?
Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights, producing a shortest-path tree.
Key Characteristics
- Finds shortest paths from a single source node to all other nodes
- Works on weighted graphs with non-negative edge weights
- Uses a greedy approach - always selects the most promising node
- Time complexity: O(V²) for simple implementation, O(E + V log V) with priority queue
Common Applications
- Network routing protocols
- Geographic navigation systems
- Traffic management systems
- Pathfinding in games
How Dijkstra's Algorithm Works
flowchart TD
A[Initialize distances: 0 for source, ∞ for others] --> B[Select node with smallest tentative distance]
B --> C[Mark node as visited]
C --> D[Update distances to neighbors]
D --> E{All nodes visited?}
E -->|No| B
E -->|Yes| F[Return shortest paths]
Step-by-Step Process
- Assign to every node a tentative distance value (0 for source, ∞ for others)
- Mark all nodes as unvisited
- Select the unvisited node with smallest tentative distance
- For current node, calculate distances to all unvisited neighbors
- If calculated distance is less than current tentative distance, update it
- Mark current node as visited
- Repeat until all nodes are visited or target node is visited
Visual Example
Algorithm in Action
Current Node
Visited Node
Shortest Path
Current State:
Initializing algorithm...
Priority Queue
Queue will appear here
Distance Table
| Node | Distance | Previous |
|---|
Implementation Details
Pseudocode
function Dijkstra(Graph, source):
create vertex set Q
for each vertex v in Graph:
dist[v] ← INFINITY
prev[v] ← UNDEFINED
add v to Q
dist[source] ← 0
while Q is not empty:
u ← vertex in Q with min dist[u]
remove u from Q
for each neighbor v of u:
alt ← dist[u] + length(u, v)
if alt < dist[v]:
dist[v] ← alt
prev[v] ← u
return dist[], prev[]
Time Complexity
The time complexity depends on the data structure used:
- Array implementation: O(V²)
- Binary heap: O((V + E) log V)
- Fibonacci heap: O(E + V log V)
Space Complexity
O(V) for storing distances and previous nodes
Limitations and Variations
Limitations
- Doesn't work with negative edge weights
- Not efficient for very large graphs (consider A* for pathfinding)
- Single-source only (for all-pairs, consider Floyd-Warshall)
Variations
- A* Algorithm: Uses heuristics for faster pathfinding
- Bidirectional Dijkstra: Searches from both start and end
- Dial's Algorithm: Optimized for small integer weights