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.
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.
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)
O((V + E) log V) with a Binary Min-Heap.O(V + E) for adjacency list and distance array.O(V × E)) when negative edges exist.Use Dijkstra for GPS routing and network packet routing. Next, let's explore Disjoint Set Union (Union-Find)!
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.
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.
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.