Dijkstra's Algorithm
Finds shortest path from source to all vertices in weighted graph with non-negative edges. Uses greedy approach with priority queue.
Visualization
Interactive visualization for Dijkstra's Algorithm
Dijkstra's Algorithm Visualization
Interactive visualization with step-by-step execution
Implementation
1function dijkstra(graph: number[][][], start: number): number[] {
2 const n = graph.length;
3 const dist = new Array(n).fill(Infinity);
4 const visited = new Array(n).fill(false);
5 dist[start] = 0;
6
7 for (let i = 0; i < n; i++) {
8 let u = -1;
9 for (let j = 0; j < n; j++) {
10 if (!visited[j] && (u === -1 || dist[j] < dist[u])) u = j;
11 }
12
13 if (dist[u] === Infinity) break;
14 visited[u] = true;
15
16 for (const [v, weight] of graph[u]) {
17 if (dist[u] + weight < dist[v]) {
18 dist[v] = dist[u] + weight;
19 }
20 }
21 }
22
23 return dist;
24}Deep Dive
Theoretical Foundation
Dijkstra's Algorithm, invented by Edsger W. Dijkstra in 1956, finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a greedy approach, maintaining a set of vertices whose shortest distance from the source is known. The algorithm repeatedly selects the unvisited vertex with the smallest known distance, marks it as visited, and updates the distances to its neighbors. Using a priority queue (min-heap) optimizes extraction of the minimum distance vertex, achieving O((V + E) log V) time complexity. The algorithm is fundamental in computer science and powers many real-world navigation and routing systems.
Complexity
Time
O((V + E) log V)
O((V + E) log V)
O((V + E) log V)
Space
O(V)
Applications
Industry Use
GPS navigation and route planning (Google Maps, Waze)
Network routing protocols (OSPF, IS-IS)
Transportation and logistics optimization
Social network analysis (shortest connection paths)
Game AI pathfinding (before A* became popular)
Telecommunications network optimization
Flight path planning
Robot navigation and motion planning
Network packet routing on the Internet
Use Cases
Related Algorithms
Depth-First Search (DFS)
Graph traversal exploring as deep as possible before backtracking. DFS is a fundamental algorithm that uses a stack (either implicitly through recursion or explicitly) to explore graph vertices. It's essential for cycle detection, topological sorting, and pathfinding problems.
Breadth-First Search (BFS)
Level-by-level graph traversal guaranteeing shortest paths in unweighted graphs. BFS uses a queue to explore vertices level by level, making it optimal for finding shortest paths and solving problems that require exploring nearest neighbors first.
Floyd-Warshall Algorithm
Floyd-Warshall is an all-pairs shortest path algorithm that finds shortest distances between every pair of vertices in a weighted graph. Unlike Dijkstra (single-source), it computes shortest paths from all vertices to all other vertices simultaneously. The algorithm can handle negative edge weights but not negative cycles. Developed independently by Robert Floyd, Bernard Roy, and Stephen Warshall in the early 1960s.
Kruskal's Algorithm
Minimum Spanning Tree algorithm using greedy approach and Union-Find data structure. Sorts edges by weight and selects minimum weight edges that don't create cycles. Named after Joseph Kruskal, it's one of the most efficient MST algorithms for sparse graphs.