Dijkstra's Algorithm
Find shortest paths from a source node using a priority queue.
How it works
Dijkstra's algorithm finds the shortest path from a source node to every other node in a graph with non-negative edge weights. It works by greedily relaxing edges: at each step it picks the unvisited node with the smallest tentative distance, then updates the distances to its neighbors if a cheaper route is found through it. This greedy choice is safe because all edge weights are non-negative — once a node is settled, no future relaxation can improve its distance.
Unlike BFS, which treats all edges as having equal cost, Dijkstra accounts for weight differences. A naive BFS on a weighted graph would find the fewest-hop path, not the cheapest one — the two can be completely different. The priority queue (min-heap) is the key data structure: it allows the algorithm to always pull the globally cheapest unfinished node in O(log V) time, giving an overall complexity of O((V + E) log V) with a binary heap.
The algorithm terminates as soon as the destination node is popped from the priority queue, at which point its tentative distance is finalized and the shortest path can be reconstructed by following parent pointers back to the source. The trade-off versus Bellman-Ford is that Dijkstra is faster but cannot handle negative-weight edges; for those, Bellman-Ford or SPFA must be used instead.
Complexity
Visualizer
Where it's used in the real world
GPS navigation (Google Maps / Waze)
Turn-by-turn shortest or fastest route computationRoad networks are weighted graphs where edge weights represent travel time or distance. Dijkstra (or its A* variant with a heuristic) is run on a compressed graph of road segments to find the optimal route in milliseconds, even across continent-scale maps.
OSPF routing protocol
Computing the shortest-path tree inside an autonomous systemOpen Shortest Path First is the dominant interior gateway protocol in enterprise and ISP networks. Every router runs Dijkstra on its local link-state database to build a forwarding table that sends each packet along the cheapest path measured in link cost.
Network packet routing in ISPs
Traffic engineering and MPLS label-switched path selectionISPs use Dijkstra-based Constrained Shortest Path First (CSPF) to pre-compute explicit traffic-engineering tunnels that satisfy bandwidth and latency constraints, directing large flows along least-cost paths while avoiding congested or expensive links.
Implementation
// Simple O(V²) version — clear for learning; swap sorted array for a real heap in prod
function dijkstra(
nodes: string[],
edges: { from: string; to: string; weight: number }[],
start: string,
end: string
): { dist: number; path: string[] } {
const INF = Infinity;
const dist: Record<string, number> = Object.fromEntries(nodes.map(n => [n, INF]));
const parent: Record<string, string | null> = Object.fromEntries(nodes.map(n => [n, null]));
const visited = new Set<string>();
// Adjacency list (undirected)
const adj = new Map<string, Array<{ to: string; w: number }>>();
for (const n of nodes) adj.set(n, []);
for (const { from, to, weight } of edges) {
adj.get(from)!.push({ to, w: weight });
adj.get(to)!.push({ to: from, w: weight });
}
dist[start] = 0;
// Priority queue as sorted array
let pq: Array<{ id: string; d: number }> = [{ id: start, d: 0 }];
while (pq.length > 0) {
pq.sort((a, b) => a.d - b.d);
const { id: u, d: uDist } = pq.shift()!;
if (visited.has(u)) continue;
visited.add(u);
if (u === end) break;
for (const { to: v, w } of adj.get(u)!) {
if (visited.has(v)) continue;
const nd = uDist + w;
if (nd < dist[v]) {
dist[v] = nd;
parent[v] = u;
pq.push({ id: v, d: nd });
}
}
}
// Reconstruct path
const path: string[] = [];
for (let cur: string | null = end; cur !== null; cur = parent[cur]) {
path.unshift(cur);
}
return { dist: dist[end], path: dist[end] === INF ? [] : path };
}