Get started

Shortest Path Coding Problems: 7 Questions with Solutions

7 shortest path coding problems — 4 medium · 3 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 6-day plan.

  • Problems: 7
  • By difficulty: 4 medium · 3 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

A shortest-path algorithm finds the cheapest route between nodes when edges carry costs — travel times, prices, obstacles to remove. Breadth-first search already solves it when every edge costs the same; with different non-negative weights, Dijkstra's algorithm settles nodes in order of distance using a priority queue; with negative weights or a limit on the number of edges, Bellman–Ford relaxes every edge round by round. The problems here practise choosing between them, running them on grids as well as edge lists, and counting or constraining the shortest routes as well as measuring them.

How shortest path works, step by step

4215810232Ad=0Bd=3Cd=2Dd=8Ed=10Fd=11settled: A=0 C=2 B=3 D=8 E=10 F=11unsettled: none
Shortest paths from A in a weighted graph, with Dijkstra's algorithm. Example: edges = A→B 4, A→C 2, C→B 1, B→D 5, C→D 8, C→E 10, D→E 2, D→F 3, E→F 2; source = A
  1. Each node carries a tentative distance from A: 0 for A itself, ∞ for the rest. Every step settles the unsettled node with the smallest one; with no negative weights, no path found later can undercut it.
  2. Settle A at 0, the only finite distance left. Relaxing its edges: B gets 0 + 4 = 4; C gets 0 + 2 = 2.
  3. Settle C at 2, the smallest unsettled distance (B 4, C 2). Relaxing its edges: B drops from 4 to 2 + 1 = 3; D gets 2 + 8 = 10; E gets 2 + 10 = 12. A path with more edges can still weigh less.
  4. Settle B at 3, the smallest unsettled distance (B 3, D 10, E 12). Relaxing its edges: D drops from 10 to 3 + 5 = 8.
  5. Settle D at 8, the smallest unsettled distance (D 8, E 12). Relaxing its edges: E drops from 12 to 8 + 2 = 10; F gets 8 + 3 = 11.
  6. Settle E at 10, the smallest unsettled distance (E 10, F 11). Relaxing its edges: F would get 10 + 2 = 12, no better than 11, so it keeps 11.
  7. Settle F at 11, the last node left. It has no edges to unsettled nodes, so nothing is relaxed, and every node is now settled.
  8. Every distance is final: B 3, C 2, D 8, E 10, F 11. Following each node's last improving edge back gives the shortest path to F, A → C → B → D → F, cost 11. With a binary heap this is O((V + E) log V).

Shortest Path study plan

All 7 Shortest Path problems (4 medium and 3 hard) over 6 days, about 5 h 5 min in all — the pattern first, then easiest to hardest. Then move on to Minimum Spanning Tree.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

Day 2

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 5

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 6

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Minimum Spanning Tree

Shortest Path: the essentials

When to reach for it

Weighted edges and the cheapest route: a signal reaching every node, the cheapest flight, the fewest obstacles removed. The weights choose the algorithm. All equal: Breadth-First Search. Only 0 and 1: a deque, 0-cost moves pushed at the front. Non-negative: Dijkstra. Negative, or a cap on edges: Bellman–Ford. All pairs on a few hundred nodes: Floyd–Warshall.

The pattern

Dijkstra keeps a heap of (distance, node) pairs. Pop the smallest, skip it if stale (larger than the distance recorded), and otherwise relax each outgoing edge, pushing any neighbour whose distance improves. A node's distance is final when first popped, which needs every weight to be non-negative.

import heapq

def dijkstra(adj, src):                 # adj[u] = [(v, w), ...] with w >= 0
    dist, heap = {src: 0}, [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue        # a stale entry
        for v, w in adj[u]:
            if d + w < dist.get(v, float("inf")):
                dist[v] = d + w
                heapq.heappush(heap, (d + w, v))
    return dist

Cost

Dijkstra with a binary heap is O((V + E) log V) time and O(V + E) space. 0-1 BFS is O(V + E). Bellman–Ford is O(V × E), or O(k × E) for k rounds. Floyd–Warshall is O(V³).

Common mistakes

  • Dijkstra with a negative edge, after which a popped distance is no longer final.
  • Marking a node done when it is first pushed, as BFS does; a cheaper route to it can turn up later.
  • "At most k stops" by Dijkstra on distance alone, which discards a dearer route with stops to spare; run k + 1 Bellman–Ford rounds, each reading the previous round's copy.
  • INT_MAX as infinity plus a weight, which overflows in Java or C++.

Start with

All shortest path problems

Medium (4)

Hard (3)

Companies that ask shortest path problems

  • Amazon 5 problems on shortest path
  • Google 5 problems on shortest path
  • Microsoft 4 problems on shortest path
  • Meta 1 problem on shortest path

Next topic: Minimum Spanning Tree