Shortest Path Algorithms: Dijkstra, Bellman-Ford & Floyd-Warshall Explained

Shortest path questions are the point where graph interviews move from "can you traverse" to "can you reason about correctness". Anyone can memorise Dijkstra. The interviewer wants to know whether you understand why it works, when it silently gives wrong answers, and what to use instead. That is what this guide focuses on, with complete code in Java, C++ and Python for each algorithm.

If BFS and DFS are not yet second nature, start with graph BFS and DFS interview problems; everything here builds on BFS.

Which Shortest Path Algorithm Should You Use?

You can almost always choose from the constraints before reading the rest of the problem.

The last row is worth remembering: on a DAG you can process vertices in topological order and relax each edge once, which handles negative weights in linear time and also gives longest paths (negate the weights).

Relaxation: The One Idea Behind All of Them

Every shortest path algorithm keeps a tentative distance dist[v] for each vertex, initialised to infinity except dist[source] = 0. Relaxing edge (u, v) with weight w means:

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w
    parent[v] = u          # optional: to reconstruct the path

Relaxation never makes a distance wrong; it only lowers an upper bound to a smaller upper bound. The algorithms differ in the order in which they relax edges and therefore in how many relaxations they need before every bound is tight:

• Dijkstra relaxes edges out of vertices in increasing order of distance, so each edge is relaxed once.
• Bellman-Ford relaxes every edge, V−1 times, in arbitrary order.
• DAG shortest path relaxes edges in topological order, once each.
• Floyd-Warshall relaxes pairs (i, j) through every possible intermediate vertex k.

To print the path, keep parent[v] and walk back from the target, then reverse. Interviewers sometimes ask for the path after you return the distance; storing parents up front costs one line.

Dijkstra's Algorithm: Code, Dry Run and Proof Sketch

Dijkstra keeps a min-heap of (distance, vertex). Repeatedly pop the vertex with the smallest tentative distance. Its distance is now final. Relax all its outgoing edges, pushing any improved neighbour.

Why the greedy choice is safe

Suppose u is popped with distance d, but some true shortest path to u is shorter than d. That path leaves the set of finalised vertices at some edge (x, y) where y is not yet final. Since x is final, y was relaxed to at most dist[x] + w(x,y), which is at most the length of that path, which is less than d. With non-negative weights, the rest of the path from y to u can only add length, so y's tentative distance is less than d, and the heap would have popped y before u. Contradiction. The proof uses non-negativity in exactly one place, which is why negative edges break it.

// adj[u] = list of {v, w}
long[] dijkstra(List<int[]>[] adj, int src) {
    int n = adj.length;
    long[] dist = new long[n];
    Arrays.fill(dist, Long.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
    pq.offer(new long[]{0, src});
    while (!pq.isEmpty()) {
        long[] top = pq.poll();
        long d = top[0];
        int u = (int) top[1];
        if (d > dist[u]) continue;              // stale heap entry
        for (int[] e : adj[u]) {
            int v = e[0], w = e[1];
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.offer(new long[]{dist[v], v});
            }
        }
    }
    return dist;
}

vector<long long> dijkstra(const vector<vector<pair<int,int>>>& adj, int src) {
    const long long INF = LLONG_MAX;
    vector<long long> dist(adj.size(), INF);
    using P = pair<long long, int>;
    priority_queue<P, vector<P>, greater<P>> pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

import heapq

def dijkstra(adj, src, n):
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

Dry run on edges 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), source 0:

Complexity: every edge can push one heap entry, so the heap holds O(E) items and the total is O(E log E) = O(E log V) (since E ≤ V², log E ≤ 2 log V), plus O(V) to initialise. A Fibonacci heap gives O(E + V log V) in theory, but nobody implements one in an interview; mention it only if asked. For dense graphs (E ≈ V²), the array-based O(V²) Dijkstra without a heap is actually faster.

The stale-entry check (if d > dist[u]: continue) is the lazy-deletion technique described in the heap and priority queue guide. Without it the algorithm stays correct but may relax the same vertex's edges many times.

Why Negative Edges Break Dijkstra (Concrete Counterexample)

Edges: A→B (2), A→C (3), C→B (−2). True shortest distance to B is 3 − 2 = 1.

1. Pop A (0). dist[B] = 2, dist[C] = 3.
2. Pop B (2). Textbook Dijkstra marks B final at 2.
3. Pop C (3). Relax C→B: 3 − 2 = 1 < 2. But B is already final; with a visited set the update is ignored and the answer 2 is wrong.

The lazy version without a visited set would push (1, B) again and re-process B, which happens to fix this tiny example. But it no longer guarantees each vertex is processed once, and on adversarial graphs the number of re-processings can grow exponentially. So the honest interview answer is: "Dijkstra requires non-negative weights. With negatives, use Bellman-Ford, or topological-order relaxation if the graph is a DAG."

0-1 BFS: Shortest Paths with 0/1 Weights in Linear Time

When every edge costs 0 or 1, you can avoid the heap. Use a double-ended queue. Relaxing a 0-weight edge puts the neighbour at the front (same distance as the current vertex); relaxing a 1-weight edge puts it at the back. The deque then contains at most two distinct distances, d and d+1, in order, which is exactly the invariant a priority queue would maintain.

Classic problem: Minimum Obstacle Removal to Reach Corner (2290). Moving into an empty cell costs 0, moving into an obstacle costs 1 (you remove it).

int minimumObstacles(vector<vector<int>>& grid) {
    int R = grid.size(), C = grid[0].size();
    vector<vector<int>> dist(R, vector<int>(C, INT_MAX));
    deque<pair<int,int>> dq;
    dist[0][0] = 0;
    dq.push_back({0, 0});
    int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    while (!dq.empty()) {
        auto [r, c] = dq.front();
        dq.pop_front();
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            int w = grid[nr][nc];
            if (dist[r][c] + w < dist[nr][nc]) {
                dist[nr][nc] = dist[r][c] + w;
                if (w == 0) dq.push_front({nr, nc});
                else dq.push_back({nr, nc});
            }
        }
    }
    return dist[R - 1][C - 1];
}

O(R·C) time. A vertex may be pushed more than once (when its distance improves), but at most twice per incoming edge, so the bound holds. Minimum Cost to Make at Least One Valid Path in a Grid (1368) is the same pattern: following the arrow costs 0, changing direction costs 1.

Bellman-Ford: Negative Weights and Negative Cycle Detection

Bellman-Ford relaxes every edge, V−1 times. Why V−1? A shortest path without cycles has at most V−1 edges. After round i, every vertex whose shortest path uses at most i edges has its correct distance (by induction: the i-th edge of that path gets relaxed in round i, if not earlier). So after V−1 rounds, all distances are final, provided no negative cycle is reachable.

If a V-th round still relaxes some edge, a shorter path with V or more edges exists, which must repeat a vertex, meaning it contains a negative cycle.

// edges[i] = {u, v, w}; returns null if a negative cycle is reachable from src
long[] bellmanFord(int n, int[][] edges, int src) {
    final long INF = Long.MAX_VALUE / 4;
    long[] dist = new long[n];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    for (int round = 0; round < n - 1; round++) {
        boolean changed = false;
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                changed = true;
            }
        }
        if (!changed) break;                    // early exit: already converged
    }
    for (int[] e : edges) {
        if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return null;
    }
    return dist;
}

def bellman_ford(n, edges, src):
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None                     # negative cycle reachable
    return dist

The dist[u] != INF guard matters: without it, an unreachable u with a negative outgoing edge would "improve" v to INF − 5, which is garbage (and in Java/C++ with Integer.MAX_VALUE would overflow into a negative number).

Where it appears: currency arbitrage (edge weight = −log(rate); a negative cycle means profit), detecting inconsistent constraints in systems of difference constraints, and any problem with a hop limit. SPFA (queue-based Bellman-Ford that only re-relaxes vertices whose distance changed) is faster on average but has the same O(V·E) worst case; it is popular in competitive programming and rarely needed in interviews.

Cheapest Flights Within K Stops (LeetCode 787): Bellman-Ford with a Hop Limit

This is probably the most-asked shortest path problem that is not plain Dijkstra. You need the cheapest price from src to dst using at most K stops, which means at most K+1 edges.

Bellman-Ford's round structure maps perfectly: after round i, dist holds the cheapest cost using at most i edges, provided each round reads only the previous round's values. That requires copying the array each round; otherwise one round can chain several edges together and violate the limit.

def find_cheapest_price(n, flights, src, dst, k):
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    for _ in range(k + 1):                 # at most k+1 edges
        nxt = dist[:]                      # read old, write new
        for u, v, price in flights:
            if dist[u] != INF and dist[u] + price < nxt[v]:
                nxt[v] = dist[u] + price
        dist = nxt
    return dist[dst] if dist[dst] != INF else -1

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    final int INF = Integer.MAX_VALUE;
    int[] dist = new int[n];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    for (int round = 0; round <= k; round++) {
        int[] next = dist.clone();
        for (int[] f : flights) {
            int u = f[0], v = f[1], p = f[2];
            if (dist[u] != INF && dist[u] + p < next[v]) next[v] = dist[u] + p;
        }
        dist = next;
    }
    return dist[dst] == INF ? -1 : dist[dst];
}

Why the copy matters, concretely: flights 0→1 (100), 1→2 (100), 0→2 (500), K = 0. Without the copy, the first round could set dist[1] = 100 and then, in the same round, dist[2] = 200 via 1, a route with one stop, which K = 0 forbids. The correct answer is 500. With the copy, round 1 reads dist[1] = ∞ and only the direct flight counts.

Complexity O(K · E). The alternative is Dijkstra over states (city, stops used), which is also accepted; the Bellman-Ford version is shorter and easier to prove correct.

Floyd-Warshall: All-Pairs Shortest Paths

Floyd-Warshall is dynamic programming. Let dist_k[i][j] be the shortest path from i to j using only vertices 0..k as intermediates. Either the best path does not use k, or it goes i→k→j:

dist_k[i][j] = min(dist_(k-1)[i][j], dist_(k-1)[i][k] + dist_(k-1)[k][j])

Because row k and column k do not change during iteration k (going through k to reach k gains nothing when there are no negative cycles), you can update a single 2D array in place. The intermediate vertex k must be the outermost loop; putting it inside is a classic bug that produces wrong answers.

// dist[i][j] = weight of edge i->j, 0 on diagonal, INF if no edge
void floydWarshall(vector<vector<long long>>& dist) {
    const long long INF = LLONG_MAX / 4;
    int n = dist.size();
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++) {
            if (dist[i][k] == INF) continue;
            for (int j = 0; j < n; j++) {
                if (dist[k][j] == INF) continue;
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    // negative cycle check: any dist[i][i] < 0
}

def find_the_city(n, edges, threshold):
    INF = float("inf")
    d = [[INF] * n for _ in range(n)]
    for i in range(n):
        d[i][i] = 0
    for u, v, w in edges:
        d[u][v] = d[v][u] = min(d[u][v], w)
    for k in range(n):
        dk = d[k]
        for i in range(n):
            dik = d[i][k]
            if dik == INF:
                continue
            di = d[i]
            for j in range(n):
                if dik + dk[j] < di[j]:
                    di[j] = dik + dk[j]
    best, best_count = -1, INF
    for i in range(n):
        cnt = sum(1 for j in range(n) if j != i and d[i][j] <= threshold)
        if cnt <= best_count:              # ties go to the larger index
            best, best_count = i, cnt
    return best

Complexity: O(V³) time, O(V²) space. With V = 100 that is 10⁶ operations, trivial. With V = 500 it is 1.25 × 10⁸, fine in C++ and Java but slow in pure Python. Beyond that, run Dijkstra from each vertex: O(V · E log V), which wins on sparse graphs.

Floyd-Warshall also computes transitive closure (replace min/+ with OR/AND), which solves Course Schedule IV (1462): "is course a a prerequisite of course b?" for many queries.

Dijkstra Variants Interviewers Love

Once you know the template, most "hard" shortest path questions are small modifications. The key insight each time: change what "distance" means, or add information to the state.

Different path cost functions

• Path With Minimum Effort (1631): the cost of a path is its maximum edge (height difference), not the sum. Replace d + w with max(d, w). Dijkstra still works because max is monotone: extending a path never decreases its cost.
• Swim in Rising Water (778): same idea; the cost is the maximum elevation on the path.
• Path with Maximum Probability (1514): maximise the product of probabilities in [0, 1]. Use a max-heap and multiply; extending a path never increases probability, which is the mirror of non-negativity. Alternatively take −log(p) to convert to a sum of non-negative weights.

Augmented state

• Shortest path with K stops / fuel / discounts: state becomes (node, resource used). The graph is now V·K states; Dijkstra on it costs O(E·K log(V·K)).
• Shortest Path Visiting All Nodes (847): state is (node, bitmask of visited nodes), BFS over 2ⁿ·n states. Bitmask tricks are in bit manipulation for coding interviews.
• Number of Ways to Arrive at Destination (1976): run Dijkstra and also keep ways[v]. When you find a strictly shorter distance, set ways[v] = ways[u]; when equal, add ways[u]. Take results mod 10⁹+7.

Network Delay Time (743): the warm-up

Run Dijkstra from k; the answer is the maximum finite distance, or −1 if some node is unreachable. It is the most direct Dijkstra question and often the first one asked to check you know the template.

public int networkDelayTime(int[][] times, int n, int k) {
    List<int[]>[] adj = new ArrayList[n + 1];
    for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
    for (int[] t : times) adj[t[0]].add(new int[]{t[1], t[2]});
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    pq.offer(new int[]{0, k});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];
        if (d > dist[u]) continue;
        for (int[] e : adj[u]) {
            if (d + e[1] < dist[e[0]]) {
                dist[e[0]] = d + e[1];
                pq.offer(new int[]{dist[e[0]], e[0]});
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) return -1;
        ans = Math.max(ans, dist[i]);
    }
    return ans;
}

Complexity Comparison at a Glance

How to Handle Shortest Path Questions in Interviews

Shortest path questions are popular at companies whose products are literally graphs: Uber, Ola, Swiggy, Zomato, Google Maps, airline and logistics companies. The system design version (routing at scale) is covered in Design Uber / Ola; in the coding round, the interviewer typically probes:

Before coding, state the model in one sentence: "Nodes are cities, directed edges are flights weighted by price, and the state needs the number of stops because of the K limit." That sentence alone often decides between a correct and a subtly wrong solution.

Common Shortest Path Mistakes

• Overflow from INF. Integer.MAX_VALUE + w wraps to a negative number and becomes the "shortest" distance. Use long, guard with dist[u] != INF, or use INF = 1e9 / LLONG_MAX / 4 so additions stay safe.
• Marking visited on push in Dijkstra. That is correct for BFS, wrong for Dijkstra: a vertex's distance can still improve after it is first pushed. Finalise on pop.
• Missing the stale-entry check, so the same vertex's edges are relaxed many times. Correct but slow; on large tests it can time out.
• Not copying the array in K-limited Bellman-Ford.
• Putting k inside the i/j loops in Floyd-Warshall.
• 1-indexed nodes (Network Delay Time uses 1..n). Size arrays n+1.
• Using Dijkstra for longest path. Longest simple path is NP-hard in general graphs; on a DAG, negate weights and use topological relaxation.
• Undirected edges added once. Add both directions.

Shortest Path Practice Problems (In Order)

Pair this list with union-find problems (minimum spanning trees are the other half of weighted-graph interviews) and you will have covered weighted graphs end to end. For an ordering of all DSA topics, see the top DSA patterns guide.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.