Dijkstra's Algorithm
info
Dijkstra's algorithm finds the shortest path between nodes in a weighted graph, which may represent, for example, road networks.
Interactive Visualization
Try Dijkstra's algorithm on this interactive graph:
How Dijkstra's Algorithm Works
The algorithm maintains a set of unvisited nodes and operates as follows:
- Initialize distances to all vertices as infinity, except the source (which is zero)
- Select the unvisited vertex with the smallest distance
- Calculate distances to all unvisited neighbors
- Update the neighbor's distance if a shorter path is found
- Mark the current vertex as visited
- Repeat until all vertices are visited
Key Characteristics
- Uses a priority queue for efficiency
- Time Complexity: O((V + E) log V) with binary heap
- Space Complexity: O(V)
- Works only with non-negative weights
- Finds the optimal (shortest) path
Common Applications
- GPS and Navigation systems
- Network routing protocols
- Social networks
- Flight scheduling
- Games (finding shortest path for NPCs)
caution
Dijkstra's algorithm doesn't work with negative edge weights. For graphs with negative weights, use the Bellman-Ford algorithm instead.