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 cost | O((V + E) log V) with a binary heap |
|---|---|
| Requirement | No negative edge weights |
| Negative edges | Bellman-Ford, O(V * E) |
| All pairs | Floyd-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
- Skip stale heap entries with a check that the popped distance is no larger than dist[u].
- Use long for distances when weights can reach 10^9 and paths have many edges.
- Do not use Dijkstra with negative weights. State why: a finalised vertex could still be improved.
- In Python, push tuples (distance, vertex) so the heap orders by distance.
- Remember the heap holds duplicates, so its size can reach E, not V.
Dijkstra and Shortest Path Interview Questions: questions with worked answers
1 Single-source shortest paths with Dijkstra
mediumKeep 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.
pythonimport 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 distjavalong[] 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 Network delay time: when does the signal reach everyone?
mediumRun 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.
pythonimport 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 -1javaint 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 Recover the actual shortest path, not just its length
mediumStore 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).
pythonimport 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]javaList<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 Path with maximum probability
mediumProbabilities 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.
pythonimport 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.0javadouble 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 Path with minimum effort in a grid
mediumEffort 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.
pythonimport 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 0javaint 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 Swim in rising water
mediumAt 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.
pythonimport 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))javaint 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 Number of ways to reach the destination by a shortest path
hardRun 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.
pythonimport 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]javaint 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 Cheapest flight within at most K stops
hardPlain 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.
pythondef 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]javaint 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 City with the fewest neighbours within a distance threshold
hardCompute 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.
pythondef 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 ansjavaint 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 Bellman-Ford with negative edges and negative cycle detection
hardRelax 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.
pythondef 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 distjavalong[] 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
- Divide and Conquer Interview Questions
- Dynamic Programming Interview Questions
- Edit Distance and String DP Interview Questions
- Fast and slow pointers interview questions with solutions
- Fenwick Tree (Binary Indexed Tree) Interview Questions
- Graph Interview Questions and Answers
- Greedy algorithm interview questions with worked solutions
- Grid and Matrix DP Interview Questions
- Hashing interview questions with worked solutions
- Heap and Priority Queue Interview Questions
- Interval DP Interview Questions
- Interval interview questions with worked solutions