Master Dijkstra's greedy algorithm with priority queues to find the shortest path in non-negative weighted graphs in O(E log V) time.
Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.
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)
Use Dijkstra for GPS routing and network packet routing. Next, let's explore Disjoint Set Union (Union-Find)!