Dijkstra's Algorithm: Weighted Shortest Path
Quick Overview
Dijkstra always expands the closest unvisited node, so the first time it reaches a vertex that distance is already final. The guarantee holds in `O(E log V)` and breaks the moment an edge weight goes negative.
Deep Dive
1. Weighted Shortest Path Problem
When graph edges have weights (such as road distances, network latency, or flight costs), simple BFS cannot find the shortest path. Dijkstra's Algorithm finds the shortest path from a starting source node to all other nodes in a graph with non-negative edge weights.
2. The Greedy Relaxation Pattern
Dijkstra maintains a shortest distance table and iteratively selects the unvisited node with the smallest tentative distance using a Min-Priority Queue:
function dijkstra(numVertices, edges, startNode) {
// 1. Build Adjacency List: node -> [[neighbor, weight], ...]
const adjList = new Map();
for (let i = 0; i < numVertices; i++) adjList.set(i, []);
for (const [u, v, weight] of edges) {
adjList.get(u).push([v, weight]);
adjList.get(v).push([u, weight]); // Undirected
}
// 2. Initialize distances table with Infinity
const distances = new Array(numVertices).fill(Infinity);
distances[startNode] = 0;
// 3. Min-Priority Queue storing [currentNode, currentDist]
const pq = [[startNode, 0]];
while (pq.length > 0) {
// Sort to extract smallest distance (in production, use a Binary Min-Heap!)
pq.sort((a, b) => a[1] - b[1]);
const [currNode, currDist] = pq.shift();
// Stale path optimization
if (currDist > distances[currNode]) continue;
for (const [neighbor, weight] of adjList.get(currNode)) {
const newDist = currDist + weight;
// Relaxation step: Found shorter path to neighbor!
if (newDist < distances[neighbor]) {
distances[neighbor] = newDist;
pq.push([neighbor, newDist]);
}
}
}
return distances;
}
const edges = [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5]];
console.log(dijkstra(4, edges, 0));
// Output: [0, 3, 1, 4] (Shortest paths from 0 to 0, 1, 2, 3)
3. Time & Space Complexity
- Time Complexity:
O((V + E) log V)with a Binary Min-Heap. - Space Complexity:
O(V + E)for adjacency list and distance array.
4. Common Mistakes
- Applying to Negative Edge Weights: Dijkstra's greedy assumption fails on graphs with negative edge weights! Use the Bellman-Ford Algorithm (
O(V × E)) when negative edges exist.
5. Next Steps
Use Dijkstra for GPS routing and network packet routing. Next, let's explore Disjoint Set Union (Union-Find)!
Next Up in Data Structures & Algorithms Core Patterns
Big O Notation: Time & Space Complexity
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
Dynamic Arrays & Amortized Resizing
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
Two Pointers Pattern (Converging & Symmetrical)
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.