Shortest Path Algorithms

Finding the shortest path between nodes in a graph is one of the most fundamental and frequently-interviewed graph problems. There is no single best algorithm — the right choice depends on the type of graph you are working with.

Algorithm Selection Guide

Graph type	Algorithm	Time complexity
Unweighted (all edges = 1)	BFS	O(V + E)
Weighted, no negative edges	Dijkstra	O((V+E) log V) with min-heap
Weighted, negative edges (no negative cycle)	Bellman-Ford	O(V·E)
Directed Acyclic Graph (DAG)	Topo sort + DP relaxation	O(V + E)
All-pairs shortest paths	Floyd-Warshall	O(V³)
Dense graphs (matrix)	Floyd-Warshall or Dijkstra with matrix	O(V³) or O(V²)

Approach 1 — BFS for Unweighted Graphs

BFS explores nodes level by level. Since every edge has weight 1, the first time you reach a node is via the shortest path. Track distances in an array initialised to Infinity.

function bfsShortestPath(graph, start, end) {
  const dist = new Map();
  dist.set(start, 0);
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift();
    if (node === end) return dist.get(node);

    for (const neighbour of (graph.get(node) || [])) {
      if (!dist.has(neighbour)) {
        dist.set(neighbour, dist.get(node) + 1);
        queue.push(neighbour);
      }
    }
  }
  return -1; // unreachable
}

// Example: grid shortest path
function shortestPathGrid(grid) {
  const R = grid.length, C = grid[0].length;
  if (grid[0][0] === 1 || grid[R-1][C-1] === 1) return -1;

  const queue = [[0, 0, 1]]; // [row, col, distance]
  const visited = Array.from({ length: R }, () => new Array(C).fill(false));
  visited[0][0] = true;
  const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];

  while (queue.length > 0) {
    const [r, c, d] = queue.shift();
    if (r === R-1 && c === C-1) return d;
    for (const [dr, dc] of dirs) {
      const nr = r+dr, nc = c+dc;
      if (nr>=0 && nr<R && nc>=0 && nc<C && !visited[nr][nc] && grid[nr][nc]===0) {
        visited[nr][nc] = true;
        queue.push([nr, nc, d+1]);
      }
    }
  }
  return -1;
}

Approach 2 — Dijkstra's Algorithm

Dijkstra extends BFS to weighted graphs. A min-heap (priority queue) always processes the node with the smallest known distance next — the greedy choice that guarantees correctness as long as all edge weights are non-negative.

Full implementation is on the dedicated Dijkstra page. Here is a compact version:

// Requires a MinHeap. We use a simple sorted-array simulation for brevity.
function dijkstra(graph, start) {
  // graph: Map<node, Array<[neighbour, weight]>>
  const dist = new Map();
  for (const node of graph.keys()) dist.set(node, Infinity);
  dist.set(start, 0);

  // [distance, node] — smallest distance first
  const heap = [[0, start]];

  while (heap.length > 0) {
    heap.sort((a, b) => a[0] - b[0]); // O(n log n) — real heap is O(log n)
    const [d, node] = heap.shift();

    if (d > dist.get(node)) continue; // stale entry

    for (const [neighbour, weight] of (graph.get(node) || [])) {
      const newDist = d + weight;
      if (newDist < dist.get(neighbour)) {
        dist.set(neighbour, newDist);
        heap.push([newDist, neighbour]);
      }
    }
  }
  return dist;
}

// See the Dijkstra page for O((V+E) log V) min-heap implementation

Warning

Do NOT use Dijkstra with negative edge weights — it will produce incorrect results. Use Bellman-Ford instead.

Approach 3 — Bellman-Ford

Bellman-Ford relaxes all edges V−1 times. One more relaxation pass detects negative cycles. It handles negative weights at the cost of a higher time complexity: O(V·E).

Full implementation is on the dedicated Bellman-Ford page. Key idea:

function bellmanFord(vertices, edges, start) {
  // edges: Array<[u, v, weight]>
  const dist = new Array(vertices).fill(Infinity);
  dist[start] = 0;

  // V-1 relaxation passes
  for (let pass = 0; pass < vertices - 1; pass++) {
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }

  // V-th pass: if any dist still improves, a negative cycle exists
  for (const [u, v, w] of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
      return null; // negative cycle detected
    }
  }
  return dist;
}

Approach 4 — DAG Shortest Path (Topological + DP)

For Directed Acyclic Graphs with arbitrary weights (including negative), you can find shortest paths in O(V + E) — faster than both Dijkstra and Bellman-Ford:

Topologically sort the vertices.
Process vertices in topological order; for each vertex relax all outgoing edges.

Because you process dependencies first, each relaxation is permanent.

function dagShortestPath(numV, edges, start) {
  // Build adjacency list
  const graph    = Array.from({ length: numV }, () => []);
  const inDegree = new Array(numV).fill(0);
  for (const [u, v, w] of edges) {
    graph[u].push([v, w]);
    inDegree[v]++;
  }

  // Kahn's topological sort
  const queue = [];
  for (let i = 0; i < numV; i++) if (inDegree[i] === 0) queue.push(i);
  const topoOrder = [];
  while (queue.length > 0) {
    const node = queue.shift();
    topoOrder.push(node);
    for (const [next] of graph[node]) if (--inDegree[next] === 0) queue.push(next);
  }

  // Relax edges in topological order
  const dist = new Array(numV).fill(Infinity);
  dist[start] = 0;
  for (const u of topoOrder) {
    if (dist[u] === Infinity) continue;
    for (const [v, w] of graph[u]) {
      if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
    }
  }
  return dist;
}

Approach 5 — Floyd-Warshall (All-Pairs)

Floyd-Warshall computes shortest paths between every pair of vertices. It works with negative weights (but not negative cycles) and is O(V³) time, O(V²) space.

The idea: for each intermediate vertex k, check if routing through k improves the path from i to j.

function floydWarshall(dist) {
  // dist[i][j] = initial edge weight, Infinity if no direct edge, 0 on diagonal
  const V = dist.length;

  for (let k = 0; k < V; k++) {
    for (let i = 0; i < V; i++) {
      for (let j = 0; j < V; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
  // After this, dist[i][j] = shortest path from i to j
  // If dist[i][i] < 0 for any i → negative cycle exists
  return dist;
}

// Example: 4 nodes, edges 0→1 (3), 0→3 (7), 1→3 (2), 3→0 (2)
const INF = Infinity;
const d = [
  [0,   3,   INF, 7  ],
  [INF, 0,   INF, 2  ],
  [INF, INF, 0,   INF],
  [2,   INF, INF, 0  ],
];
console.log(floydWarshall(d));
// d[0][3] = 5 (0→1→3), d[3][1] = 5 (3→0→1)

Choosing the Right Algorithm

Question to ask	Algorithm
Unweighted graph?	BFS — O(V+E), simple and optimal
Weighted, all non-negative?	Dijkstra — O((V+E) log V) with heap
Negative weights present?	Bellman-Ford — O(V·E), handles negatives
Need to detect negative cycles?	Bellman-Ford — run V-th pass
Graph is a DAG?	Topo sort + DP — O(V+E), handles any weights
Need all-pairs distances?	Floyd-Warshall — O(V³), dense graphs
Source → multiple targets?	Multi-source BFS or Dijkstra from each source

Tip

In interviews: if the graph is unweighted, reach for BFS first. If weighted and non-negative, reach for Dijkstra. Justify your choice in one sentence before coding.

Practice Problems

LeetCode 1091 — Shortest Path in Binary Matrix (BFS)
LeetCode 743 — Network Delay Time (Dijkstra)
LeetCode 787 — Cheapest Flights Within K Stops (Bellman-Ford variant)
LeetCode 1514 — Path with Maximum Probability (Dijkstra, maximise)
LeetCode 1334 — Find the City With the Smallest Number of Neighbors (Floyd-Warshall)
LeetCode 399 — Evaluate Division (weighted graph + BFS/DFS)