Shortest Path: Code Templates in 6 Languages
If you have not read the concept guide yet, start there for the intuition and the algorithm-selection table. This page gives you the four templates you memorize for interviews: Dijkstra, BFS on unweighted graphs, Bellman-Ford, and Floyd-Warshall. Every template below is written to be adapted, not copied blindly. Read the comments, because they explain why each line exists, and that understanding is what survives transplanting the code into a different problem.
Main Template: Dijkstra
Dijkstra computes the shortest distance from one source to every other node in a graph with non-negative weights. The heap is the whole trick: every step it hands back the closest unsettled node, and once a node leaves the heap its distance is final.
Use this for Network Delay Time and Swim in Rising Water .
class MinHeap {
// binary min-heap over [priority, payload] pairs
constructor() { this.items = []; }
push(item) {
this.items.push(item);
let i = this.items.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.items[p][0] <= this.items[i][0]) break;
[this.items[p], this.items[i]] = [this.items[i], this.items[p]];
i = p;
}
}
pop() {
const top = this.items[0];
const last = this.items.pop();
if (this.items.length > 0) {
this.items[0] = last;
let i = 0;
while (true) {
let smallest = i;
const l = 2 * i + 1, r = 2 * i + 2;
if (l < this.items.length && this.items[l][0] < this.items[smallest][0]) smallest = l;
if (r < this.items.length && this.items[r][0] < this.items[smallest][0]) smallest = r;
if (smallest === i) break;
[this.items[i], this.items[smallest]] = [this.items[smallest], this.items[i]];
i = smallest;
}
}
return top;
}
get size() { return this.items.length; }
}
// graph[u] = list of [neighbor, weight]; returns the shortest distance
// from source to every node, or Infinity where no path exists
function dijkstra(graph, source, n) {
const dist = new Array(n).fill(Infinity);
dist[source] = 0;
const heap = new MinHeap();
heap.push([0, source]);
while (heap.size > 0) {
const [d, u] = heap.pop();
// A node can be pushed multiple times with improving distances.
// Only the best entry carries news, so skip all the others.
if (d > dist[u]) continue;
for (const [v, w] of graph[u] || []) {
const nd = d + w;
if (nd < dist[v]) {
dist[v] = nd;
heap.push([nd, v]);
}
}
}
return dist;
}Code Breakdown
Key Variables
dist: the array that stores the best known distance from source to each node. Initested as infinity for every node except the source, and only ever improved, never re-raised.heap: a binary min-heap of pending (distance, node) pairs. Always pops the node with the smallest distance, which is what turns the scan into a greedy one.graph: the adjacency list. Each entry maps a node to its (neighbor, weight) pairs. An adjacency list, not a matrix, because that keeps the space at.O(V + E)
Visual Mechanism
graph TD
A["Start with all distances = infinity"] --> B["Set dist[source] = 0, push (0, source)"]
B --> C{"Heap empty?"}
C -->|No| D["Pop (d, u)"]
D --> E{"d > dist[u]? Stale entry"}
E -->|Yes| C
E -->|No| F["For every (v, w) in graph[u]"]
F --> G{"d + w < dist[v]?"}
G -->|Yes| H["dist[v] = d + w, push (d + w, v)"]
G -->|No| I["v already has a better route"]
H --> C
I --> C
C -->|Yes| J["Return dist"]
Critical Sections
Initialization sets the source to 0 and everything else to infinity. Reading back the infinity later is how you report unreachable nodes, so keeping the sentinel distinct from a real distance matters. This becomes the bug where unreachability is checked against the wrong value.
The heap drives the whole thing. Every relaxation that improves a node pushes a fresh entry, and the heap always pops the smallest distance first. That ordering is what turns the “confirms once” property into a real guarantee, because the first time a node is popped it is popped with its final value.
The stale-entry check keeps the heap from growing without bound. Without it, the same node appears once per improvement, and in a graph where every edge keeps improving one node the heap drifts toward
Variations
1. BFS for Unweighted Graphs
When every edge costs 1, a plain FIFO queue replaces the heap, and the first time a node is discovered is the shortest path to it. This is the fastest and the least code, so it is worth reaching for first when weights are absent.
Use this for Minimum Depth of Binary Tree and Shortest Path in Binary Matrix .
// graph: adjacency list of neighbors, no weights at all
function bfsDistances(graph, source, n) {
const dist = new Array(n).fill(-1);
dist[source] = 0;
const queue = [source];
while (queue.length > 0) {
const u = queue.shift();
for (const v of graph[u] || []) {
// First discovery of a node is its shortest path.
// Later discoveries would only be longer, so skip them.
if (dist[v] === -1) {
dist[v] = dist[u] + 1;
queue.push(v);
}
}
}
return dist;
}2. Bellman-Ford for Negative Weights
Bellman-Ford relaxes every edge V - 1 times. That many passes is enough to propagate the shortest path from the source through every intermediate node, and one extra scan reveals negative cycles. This is strictly slower than Dijkstra, so it earns its place only when negative weights force it out of the reach of Dijkstra.
Use this for Cheapest Flights Within K Stops , where the stop limit becomes the iteration count.
// edges: [u, v, weight] tuples. Returns [dist, hasNegativeCycle]
function bellmanFord(edges, n, source) {
const dist = new Array(n).fill(Infinity);
dist[source] = 0;
// A path through n nodes uses at most n - 1 edges, so n - 1
// full passes push the source's influence as far as it can go.
for (let i = 0; i < n - 1; i++) {
let relaxed = false;
for (const [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
relaxed = true;
}
}
if (!relaxed) break; // nothing moved, future passes move nothing
}
// One more scan: any improvement here means a negative cycle
// can shorten paths forever.
for (const [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
return [dist, true];
}
}
return [dist, false];
}3. Floyd-Warshall for All Pairs
Floyd-Warshall fills a matrix where cell (i, j) is the shortest distance between i and j. Each of the three nesting passes lets one more intermediate node act as a bridge, and after all V passes every cell holds its final answer. There is no faster way to answer “distance between every pair” on a dense graph with small V.
Use this for Find the City With the Smallest Number of Neighbors at a Threshold Distance .
// graph: adjacency list, dist[i][dist[j] ends as the shortest i to j distance
function floydWarshall(graph, n) {
const dist = Array.from({ length: n }, () => new Array(n).fill(Infinity));
for (let i = 0; i < n; i++) dist[i][i] = 0;
for (let i = 0; i < n; i++) {
for (const [j, w] of graph[i] || []) dist[i][j] = w;
}
// Node k becomes a possible middle point. Order of the loops matters:
// all pairs must get a chance to route through k before k moves on.
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (dist[i][k] !== Infinity && dist[k][j] !== Infinity) {
const via = dist[i][k] + dist[k][j];
if (via < dist[i][j]) dist[i][j] = via;
}
}
}
}
return dist;
}Now head to the practice problems to apply these templates to real interview questions.
Now head to the practice problems to apply these templates to real interview questions.