Autocoder

Dijkstra and Shortest Path Interview Questions

Last updated 2026-11-19

Shortest path questions ask for the cheapest route through a weighted graph. Dijkstra algorithm solves them in O((V + E) log V) when no edge is negative, by always finalising the closest unfinished vertex using a min-heap. Many interview problems are Dijkstra in disguise, with a twist on what the cost means.

Below are problems that run from the plain algorithm to counting shortest paths and negative-weight handling, with Python and Java code, complexity and edge cases. Priority queue basics are on the heap interview questions page, and unweighted shortest paths on the BFS interview questions page.

Dijkstra costO((V + E) log V) with a binary heap
RequirementNo negative edge weights
Negative edgesBellman-Ford, O(V * E)
All pairsFloyd-Warshall, O(V^3)

The pattern and when to spot it

Look for a graph or grid where moves have different non-negative costs and the question asks for cheapest, fastest, least effort or highest probability. If every move costs 1, BFS is enough. If costs are only 0 or 1, 0-1 BFS with a deque is enough. Otherwise use a heap.

The idea generalises. Dijkstra works whenever the path cost combines edge costs by an operation that never improves when you extend the path. Sum gives ordinary distance, max gives minimax paths such as minimum effort and swimming in rising water, and product with values at most 1 gives maximum probability. A constraint such as at most K stops needs either extra state or a Bellman-Ford style relaxation by rounds.

Details that cost marks

Dijkstra and Shortest Path Interview Questions: questions with worked answers

  1. 1

    Single-source shortest paths with Dijkstra

    medium

    Keep a min-heap of (distance, vertex). Pop the closest vertex; if its popped distance is larger than the best known, skip it as stale. Otherwise relax each outgoing edge and push improved distances. Each vertex is finalised the first time it is popped, which is valid only when all weights are non-negative. Time O((V + E) log V), space O(V + E). Edge cases: negative weights (use Bellman-Ford), unreachable vertices keep infinity, parallel edges, stale heap entries that must be skipped.

    python
    import heapq
    def dijkstra(n, edges, src):
        g = [[] for _ in range(n)]
        for u, v, w in edges:
            g[u].append((v, w))
        dist = [float('inf')] * n
        dist[src] = 0
        h = [(0, src)]
        while h:
            d, u = heapq.heappop(h)
            if d > dist[u]:
                continue
            for v, w in g[u]:
                if d + w < dist[v]:
                    dist[v] = d + w
                    heapq.heappush(h, (dist[v], v))
        return dist
    java
    long[] dijkstra(int n, int[][] edges, int src) {
        List<List<int[]>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) g.get(e[0]).add(new int[]{e[1], e[2]});
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[src] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.add(new long[]{0, src});
        while (!pq.isEmpty()) {
            long[] t = pq.poll();
            int u = (int) t[1];
            if (t[0] > dist[u]) continue;
            for (int[] e : g.get(u))
                if (t[0] + e[1] < dist[e[0]]) {
                    dist[e[0]] = t[0] + e[1];
                    pq.add(new long[]{dist[e[0]], e[0]});
                }
        }
        return dist;
    }
  2. 2

    Network delay time: when does the signal reach everyone?

    medium

    Run Dijkstra from the source node k. The time for all nodes to receive the signal is the largest finite distance. If any node is unreachable, return -1. Time O(E log V), space O(V + E). Edge cases: unreachable node (-1), single node (0), nodes labelled from 1, directed edges.

    python
    import heapq
    def network_delay(times, n, k):
        g = [[] for _ in range(n + 1)]
        for u, v, w in times:
            g[u].append((v, w))
        dist = {}
        h = [(0, k)]
        while h:
            d, u = heapq.heappop(h)
            if u in dist:
                continue
            dist[u] = d
            for v, w in g[u]:
                if v not in dist:
                    heapq.heappush(h, (d + w, v))
        return max(dist.values()) if len(dist) == n else -1
    java
    int networkDelay(int[][] times, int n, int k) {
        List<List<int[]>> g = new ArrayList<>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
        for (int[] t : times) g.get(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) -> a[0] - b[0]);
        pq.add(new int[]{0, k});
        while (!pq.isEmpty()) {
            int[] t = pq.poll();
            if (t[0] > dist[t[1]]) continue;
            for (int[] e : g.get(t[1]))
                if (t[0] + e[1] < dist[e[0]]) { dist[e[0]] = t[0] + e[1]; pq.add(new int[]{dist[e[0]], e[0]}); }
        }
        int best = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            best = Math.max(best, dist[i]);
        }
        return best;
    }
  3. 3

    Recover the actual shortest path, not just its length

    medium

    Store a parent array: whenever a relaxation improves dist[v], set parent[v] = u. After the run, walk from the target back through parents to the source and reverse the list. If the target distance is infinity, return an empty path. Time O((V + E) log V), space O(V + E). Edge cases: unreachable target, source equal to target (path of one vertex), ties between equally short paths (any is valid unless a rule is given).

    python
    import heapq
    def shortest_path(n, edges, src, dst):
        g = [[] for _ in range(n)]
        for u, v, w in edges:
            g[u].append((v, w)); g[v].append((u, w))
        dist, parent = [float('inf')] * n, [-1] * n
        dist[src] = 0
        h = [(0, src)]
        while h:
            d, u = heapq.heappop(h)
            if d > dist[u]:
                continue
            for v, w in g[u]:
                if d + w < dist[v]:
                    dist[v], parent[v] = d + w, u
                    heapq.heappush(h, (dist[v], v))
        if dist[dst] == float('inf'):
            return []
        path, cur = [], dst
        while cur != -1:
            path.append(cur)
            cur = parent[cur]
        return path[::-1]
    java
    List<Integer> shortestPath(int n, int[][] edges, int src, int dst) {
        List<List<int[]>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) { g.get(e[0]).add(new int[]{e[1], e[2]}); g.get(e[1]).add(new int[]{e[0], e[2]}); }
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        dist[src] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.add(new long[]{0, src});
        while (!pq.isEmpty()) {
            long[] t = pq.poll();
            int u = (int) t[1];
            if (t[0] > dist[u]) continue;
            for (int[] e : g.get(u))
                if (t[0] + e[1] < dist[e[0]]) {
                    dist[e[0]] = t[0] + e[1]; parent[e[0]] = u;
                    pq.add(new long[]{dist[e[0]], e[0]});
                }
        }
        List<Integer> path = new ArrayList<>();
        if (dist[dst] == Long.MAX_VALUE) return path;
        for (int cur = dst; cur != -1; cur = parent[cur]) path.add(cur);
        Collections.reverse(path);
        return path;
    }
  4. 4

    Path with maximum probability

    medium

    Probabilities multiply along a path and each is at most 1, so a longer path never improves the product. Use Dijkstra with a max-heap on probability, starting from 1.0 at the source, and relax with prob[u] * p. The greedy finalisation is valid because multiplying by a number at most 1 never increases the value. Time O(E log V), space O(V + E). Edge cases: no path (return 0), probability 0 edges, start equals end (1.0), floating-point comparison.

    python
    import heapq
    def max_probability(n, edges, probs, start, end):
        g = [[] for _ in range(n)]
        for (a, b), p in zip(edges, probs):
            g[a].append((b, p)); g[b].append((a, p))
        best = [0.0] * n
        best[start] = 1.0
        h = [(-1.0, start)]
        while h:
            p, u = heapq.heappop(h)
            p = -p
            if u == end:
                return p
            if p < best[u]:
                continue
            for v, q in g[u]:
                if p * q > best[v]:
                    best[v] = p * q
                    heapq.heappush(h, (-best[v], v))
        return 0.0
    java
    double maxProbability(int n, int[][] edges, double[] probs, int start, int end) {
        List<List<double[]>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int i = 0; i < edges.length; i++) {
            g.get(edges[i][0]).add(new double[]{edges[i][1], probs[i]});
            g.get(edges[i][1]).add(new double[]{edges[i][0], probs[i]});
        }
        double[] best = new double[n];
        best[start] = 1.0;
        PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));
        pq.add(new double[]{1.0, start});
        while (!pq.isEmpty()) {
            double[] t = pq.poll();
            int u = (int) t[1];
            if (u == end) return t[0];
            if (t[0] < best[u]) continue;
            for (double[] e : g.get(u)) {
                double np = t[0] * e[1];
                if (np > best[(int) e[0]]) { best[(int) e[0]] = np; pq.add(new double[]{np, e[0]}); }
            }
        }
        return 0.0;
    }
  5. 5

    Path with minimum effort in a grid

    medium

    Effort of a path is the largest absolute height difference between consecutive cells. This is a minimax path, and Dijkstra still works if the cost of reaching a cell is max(current effort, step difference) instead of a sum. Pop the lowest effort cell first. Time O(R * C log(R * C)), space O(R * C). Edge cases: single cell (0), heights equal everywhere, using max rather than sum, a detour that lowers the worst step.

    python
    import heapq
    def minimum_effort(h):
        R, C = len(h), len(h[0])
        eff = [[float('inf')] * C for _ in range(R)]
        eff[0][0] = 0
        pq = [(0, 0, 0)]
        while pq:
            e, r, c = heapq.heappop(pq)
            if r == R - 1 and c == C - 1:
                return e
            if e > eff[r][c]:
                continue
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < R and 0 <= nc < C:
                    ne = max(e, abs(h[nr][nc] - h[r][c]))
                    if ne < eff[nr][nc]:
                        eff[nr][nc] = ne
                        heapq.heappush(pq, (ne, nr, nc))
        return 0
    java
    int minimumEffort(int[][] h) {
        int R = h.length, C = h[0].length;
        int[][] eff = new int[R][C];
        for (int[] row : eff) Arrays.fill(row, Integer.MAX_VALUE);
        eff[0][0] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.add(new int[]{0, 0, 0});
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!pq.isEmpty()) {
            int[] t = pq.poll();
            if (t[1] == R - 1 && t[2] == C - 1) return t[0];
            if (t[0] > eff[t[1]][t[2]]) continue;
            for (int[] d : dirs) {
                int nr = t[1] + d[0], nc = t[2] + d[1];
                if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
                int ne = Math.max(t[0], Math.abs(h[nr][nc] - h[t[1]][t[2]]));
                if (ne < eff[nr][nc]) { eff[nr][nc] = ne; pq.add(new int[]{ne, nr, nc}); }
            }
        }
        return 0;
    }
  6. 6

    Swim in rising water

    medium

    At time t you can enter any cell with height at most t. The time needed for a path is the maximum cell height along it, so the answer is the minimax path from the top-left to the bottom-right. Use a min-heap on that maximum, pop the lowest, and track the running maximum as you expand. Time O(n^2 log n), space O(n^2). Edge cases: a 1 by 1 grid (its own height), start cell being the highest, heights forming a permutation.

    python
    import heapq
    def swim(grid):
        n = len(grid)
        seen = {(0, 0)}
        pq = [(grid[0][0], 0, 0)]
        while pq:
            t, r, c = heapq.heappop(pq)
            if r == n - 1 and c == n - 1:
                return t
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen:
                    seen.add((nr, nc))
                    heapq.heappush(pq, (max(t, grid[nr][nc]), nr, nc))
    java
    int swim(int[][] g) {
        int n = g.length;
        boolean[][] seen = new boolean[n][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.add(new int[]{g[0][0], 0, 0});
        seen[0][0] = true;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!pq.isEmpty()) {
            int[] t = pq.poll();
            if (t[1] == n - 1 && t[2] == n - 1) return t[0];
            for (int[] d : dirs) {
                int nr = t[1] + d[0], nc = t[2] + d[1];
                if (nr >= 0 && nc >= 0 && nr < n && nc < n && !seen[nr][nc]) {
                    seen[nr][nc] = true;
                    pq.add(new int[]{Math.max(t[0], g[nr][nc]), nr, nc});
                }
            }
        }
        return -1;
    }
  7. 7

    Number of ways to reach the destination by a shortest path

    hard

    Run Dijkstra and also keep ways[v], the number of shortest paths to v. When you find a strictly shorter route to v, set ways[v] = ways[u]. When you find an equal-length route, add ways[u]. Take the result modulo 10^9 + 7 as problems usually require. Time O(E log V), space O(V + E). Edge cases: n equal to 1 (one way), zero-weight edges can break equal-length counting order, large counts needing a modulus and long arithmetic.

    python
    import heapq
    def count_paths(n, roads):
        MOD = 10**9 + 7
        g = [[] for _ in range(n)]
        for u, v, w in roads:
            g[u].append((v, w)); g[v].append((u, w))
        dist, ways = [float('inf')] * n, [0] * n
        dist[0], ways[0] = 0, 1
        h = [(0, 0)]
        while h:
            d, u = heapq.heappop(h)
            if d > dist[u]:
                continue
            for v, w in g[u]:
                if d + w < dist[v]:
                    dist[v], ways[v] = d + w, ways[u]
                    heapq.heappush(h, (dist[v], v))
                elif d + w == dist[v]:
                    ways[v] = (ways[v] + ways[u]) % MOD
        return ways[n - 1]
    java
    int countPaths(int n, int[][] roads) {
        final int MOD = 1_000_000_007;
        List<List<int[]>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] r : roads) { g.get(r[0]).add(new int[]{r[1], r[2]}); g.get(r[1]).add(new int[]{r[0], r[2]}); }
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        int[] ways = new int[n];
        dist[0] = 0; ways[0] = 1;
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.add(new long[]{0, 0});
        while (!pq.isEmpty()) {
            long[] t = pq.poll();
            int u = (int) t[1];
            if (t[0] > dist[u]) continue;
            for (int[] e : g.get(u)) {
                long nd = t[0] + e[1];
                if (nd < dist[e[0]]) { dist[e[0]] = nd; ways[e[0]] = ways[u]; pq.add(new long[]{nd, e[0]}); }
                else if (nd == dist[e[0]]) ways[e[0]] = (ways[e[0]] + ways[u]) % MOD;
            }
        }
        return ways[n - 1];
    }
  8. 8

    Cheapest flight within at most K stops

    hard

    Plain Dijkstra on price is wrong because a cheaper path may use too many stops. Either run Bellman-Ford for K+1 rounds, copying the distance array each round so edges only use the previous round, or run Dijkstra on states (city, stops used). The Bellman-Ford form is shorter. Time O(K * E), space O(V). Edge cases: source equals destination (0), no route within K stops (-1), copying the array each round so one round adds only one edge, K equal to 0 means direct flights only.

    python
    def cheapest_flight(n, flights, src, dst, k):
        INF = float('inf')
        dist = [INF] * n
        dist[src] = 0
        for _ in range(k + 1):
            nxt = dist[:]
            for u, v, w in flights:
                if dist[u] + w < nxt[v]:
                    nxt[v] = dist[u] + w
            dist = nxt
        return -1 if dist[dst] == INF else dist[dst]
    java
    int cheapestFlight(int n, int[][] flights, int src, int dst, int k) {
        int INF = Integer.MAX_VALUE;
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        for (int i = 0; i <= k; i++) {
            int[] nxt = dist.clone();
            for (int[] f : flights)
                if (dist[f[0]] != INF && dist[f[0]] + f[2] < nxt[f[1]]) nxt[f[1]] = dist[f[0]] + f[2];
            dist = nxt;
        }
        return dist[dst] == INF ? -1 : dist[dst];
    }
  9. 9

    City with the fewest neighbours within a distance threshold

    hard

    Compute all-pairs shortest paths, then count for each city how many others are within the threshold. Return the city with the smallest count, breaking ties by the largest index. Floyd-Warshall is simplest for n up to a few hundred; Dijkstra from every vertex is better for sparse graphs. Time O(n^3), space O(n^2). Edge cases: ties (choose the greater index), threshold smaller than every edge (all counts 0), disconnected cities.

    python
    def find_the_city(n, edges, threshold):
        INF = float('inf')
        d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
        for u, v, w in edges:
            d[u][v] = d[v][u] = min(d[u][v], w)
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if d[i][k] + d[k][j] < d[i][j]:
                        d[i][j] = d[i][k] + d[k][j]
        best, ans = n + 1, -1
        for i in range(n):
            cnt = sum(1 for j in range(n) if j != i and d[i][j] <= threshold)
            if cnt <= best:
                best, ans = cnt, i
        return ans
    java
    int findTheCity(int n, int[][] edges, int threshold) {
        int INF = 1_000_000_000;
        int[][] d = new int[n][n];
        for (int[] row : d) Arrays.fill(row, INF);
        for (int i = 0; i < n; i++) d[i][i] = 0;
        for (int[] e : edges) { d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]); d[e[1]][e[0]] = d[e[0]][e[1]]; }
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
        int best = n + 1, ans = -1;
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) if (j != i && d[i][j] <= threshold) cnt++;
            if (cnt <= best) { best = cnt; ans = i; }
        }
        return ans;
    }
  10. 10

    Bellman-Ford with negative edges and negative cycle detection

    hard

    Relax every edge V-1 times; a shortest path has at most V-1 edges, so distances are then final. Run one more pass: if any edge still improves, a negative cycle is reachable from the source. Dijkstra fails with negative edges because a vertex finalised early could later be improved. Time O(V * E), space O(V). Edge cases: negative cycle (report it), unreachable vertices stay infinite and must not be relaxed from, a negative edge in an undirected graph is itself a negative cycle.

    python
    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
    java
    long[] bellmanFord(int n, int[][] edges, int src) {
        long INF = Long.MAX_VALUE / 2;
        long[] dist = new long[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        for (int i = 0; i < n - 1; i++) {
            boolean changed = false;
            for (int[] e : edges)
                if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) {
                    dist[e[1]] = dist[e[0]] + e[2];
                    changed = true;
                }
            if (!changed) break;
        }
        for (int[] e : edges)
            if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return null;
        return dist;
    }

Frequently asked questions

Why does Dijkstra not work with negative edges?

It assumes that once a vertex is popped its distance is final. A negative edge discovered later could reduce that distance, so the greedy choice becomes invalid. Use Bellman-Ford instead.

What is the difference between Dijkstra and BFS?

BFS finds fewest edges and uses a plain queue. Dijkstra finds least total weight and uses a priority queue. With all weights equal they give the same distances.

When should I use Floyd-Warshall?

Use it when you need distances between all pairs and n is small, up to a few hundred. For sparse large graphs, run Dijkstra from every source instead.

Do coding rounds ask Dijkstra directly?

Often as a disguised variant such as network delay or minimum effort. The DSA coding round guide lists the graph patterns worth practising.

Related guides

More in DSA Interview Questions

See all in this section