Finding the shortest path between nodes is one of the most common graph problems. The algorithm we pick depends entirely on the type of graph.
In simple language, we’re asking: “What’s the cheapest/fastest way to get from A to B?” The answer depends on whether our roads have different lengths (weighted) or are all equal (unweighted).
The Decision Tree
BFS for Unweighted Graphs
When all edges have the same weight (or weight = 1), BFS naturally finds the shortest path. The first time we reach a node, that’s the shortest distance. We covered BFS in the previous topic — here we just track distances.
// Shortest path in unweighted graph using BFS
function shortestPath(graph, start, end) {
const dist = new Map([[start, 0]]);
const queue = [start];
while (queue.length > 0) {
const node = queue.shift();
if (node === end) return dist.get(end);
for (const neighbor of graph[node]) {
if (!dist.has(neighbor)) {
dist.set(neighbor, dist.get(node) + 1);
queue.push(neighbor);
}
}
}
return -1; // unreachable
}# Shortest path in unweighted graph using BFS
from collections import deque
def shortest_path(graph, start, end):
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
if node == end:
return dist[end]
for neighbor in graph[node]:
if neighbor not in dist:
dist[neighbor] = dist[node] + 1
queue.append(neighbor)
return -1 # unreachable// Shortest path in unweighted graph using BFS
int shortestPath(List<List<Integer>> graph, int start, int end) {
int[] dist = new int[graph.size()];
Arrays.fill(dist, -1);
dist[start] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
if (node == end) return dist[end];
for (int neighbor : graph.get(node)) {
if (dist[neighbor] == -1) {
dist[neighbor] = dist[node] + 1;
queue.add(neighbor);
}
}
}
return -1; // unreachable
}Dijkstra’s Algorithm
Dijkstra’s handles weighted graphs with non-negative weights. The idea: always process the node with the smallest known distance next. We use a priority queue (min-heap) to efficiently pick the closest unvisited node.
Think of it like spreading water from a source. Water always flows to the nearest unfilled spot first.
// Dijkstra's using a min-heap (priority queue)
function dijkstra(graph, start, n) {
const dist = Array(n).fill(Infinity);
dist[start] = 0;
// Min-heap: [distance, node] — JS needs a manual heap or sorted insert
const pq = [[0, start]]; // [dist, node]
while (pq.length > 0) {
pq.sort((a, b) => a[0] - b[0]); // simulating min-heap
const [d, node] = pq.shift();
if (d > dist[node]) continue; // skip outdated entry
for (const [neighbor, weight] of graph[node]) {
const newDist = d + weight;
if (newDist < dist[neighbor]) {
dist[neighbor] = newDist;
pq.push([newDist, neighbor]);
}
}
}
return dist; // dist[i] = shortest distance from start to i
}# Dijkstra's using a min-heap (priority queue)
import heapq
def dijkstra(graph, start, n):
dist = [float('inf')] * n
dist[start] = 0
pq = [(0, start)] # (distance, node)
while pq:
d, node = heapq.heappop(pq)
if d > dist[node]: # skip outdated entry
continue
for neighbor, weight in graph[node]:
new_dist = d + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return dist # dist[i] = shortest distance from start to i// Dijkstra's using a min-heap (priority queue)
int[] dijkstra(List<List<int[]>> graph, int start, int n) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
// PQ stores [distance, node]
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.add(new int[]{0, start});
while (!pq.isEmpty()) {
int[] top = pq.poll();
int d = top[0], node = top[1];
if (d > dist[node]) continue; // skip outdated
for (int[] edge : graph.get(node)) {
int newDist = d + edge[1];
if (newDist < dist[edge[0]]) {
dist[edge[0]] = newDist;
pq.add(new int[]{newDist, edge[0]});
}
}
}
return dist;
}The if (d > dist[node]) continue check is crucial. Since we can’t efficiently update entries in the priority queue, we add duplicates. This line skips stale entries where we’ve already found a better path.
Bellman-Ford Algorithm
Bellman-Ford handles negative edge weights (which Dijkstra’s can’t). It’s slower but more versatile. The idea: relax every edge V-1 times. If we can still relax after V-1 rounds, there’s a negative cycle.
// Bellman-Ford — handles negative weights
function bellmanFord(edges, n, start) {
const dist = Array(n).fill(Infinity);
dist[start] = 0;
for (let i = 0; i < n - 1; i++) { // V-1 relaxations
for (const [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w; // relax edge
}
}
}
// Check for negative cycles (one more round)
for (const [u, v, w] of edges)
if (dist[u] + w < dist[v]) return null; // negative cycle!
return dist;
}# Bellman-Ford — handles negative weights
def bellman_ford(edges, n, start):
dist = [float('inf')] * n
dist[start] = 0
for _ in range(n - 1): # V-1 relaxations
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w # relax edge
# Check for negative cycles
for u, v, w in edges:
if dist[u] + w < dist[v]:
return None # negative cycle!
return dist// Bellman-Ford — handles negative weights
int[] bellmanFord(int[][] edges, int n, int start) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
for (int i = 0; i < n - 1; i++) // V-1 relaxations
for (int[] e : edges)
if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]])
dist[e[1]] = dist[e[0]] + e[2]; // relax
// Check for negative cycles
for (int[] e : edges)
if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]])
return null; // negative cycle!
return dist;
}Quick Comparison
Interview Tips
- Unweighted graph? Just use BFS. Don’t overcomplicate it.
- Weighted with non-negative? Dijkstra’s. This is the most common interview scenario.
- Negative weights mentioned? Bellman-Ford. Rare in interviews, but know it exists.
- “Network Delay Time” (LeetCode 743) is the classic Dijkstra’s problem: find the time it takes for a signal to reach all nodes.
- Why can’t Dijkstra’s handle negative weights? Once we mark a node as “done” (shortest distance found), we never revisit it. A negative edge could later provide a shorter path, breaking this assumption.
Most interview shortest path problems boil down to Dijkstra’s with a priority queue. Get that implementation solid, and we’re covered for 90% of cases.