35.09Intermediate / Advanced4 topics16 min1 interactive animation

Other shortest-path topics

Four extensions of shortest-path search: bidirectional BFS and Dijkstra, which grow two searches towards each other, k shortest paths, and shortest paths with more than one criterion.

Learning goals

Run two searches and stop correctly when they meet
State the stopping rule of bidirectional Dijkstra
Describe how to get the k cheapest walks and how Yen's algorithm differs
Keep a Pareto front when each edge has two costs

Prerequisites

Dijkstra's algorithmBreadth-first search

One search balloons as it grows; two smaller searches meeting in the middle touch far fewer vertices. And real routing rarely has one cost: a route can be cheap or fast, and sometimes you need the second best.

35.09.1

Bidirectional BFS

Run one BFS from the source and another from the target, always expanding the side with the smaller frontier, one whole layer at a time. When a vertex found by one side is already known to the other, the searches touch. Finish the current layer and take the smallest total over all touching edges: the exact distance.

If the shortest distance is d and each vertex has about b neighbours, one BFS reaches about b^d vertices, while two searches of depth d / 2 reach about 2 b^(d/2). The saving depends on the graph, and is large for branching graphs. The animation prints how many vertices were expanded.

Java

1static int bidirectional(List<List<Integer>> g, int s, int t) {   // fewest edges, or -1; undirected graph
2    if (s == t) return 0;
3    int n = g.size();
4    int[] ds = new int[n], dt = new int[n];
5    Arrays.fill(ds, -1);
6    Arrays.fill(dt, -1);
7    ds[s] = 0;
8    dt[t] = 0;
9    List<Integer> fs = List.of(s), ft = List.of(t);
10    while (!fs.isEmpty() && !ft.isEmpty()) {
11        boolean fromS = fs.size() <= ft.size();                   // expand the smaller frontier
12        List<Integer> frontier = fromS ? fs : ft;
13        int[] mine = fromS ? ds : dt, other = fromS ? dt : ds;
14        List<Integer> next = new ArrayList<>();
15        int best = Integer.MAX_VALUE;
16        for (int u : frontier)
17            for (int v : g.get(u)) {
18                if (other[v] != -1) best = Math.min(best, mine[u] + 1 + other[v]);   // the two searches touch
19                if (mine[v] == -1) { mine[v] = mine[u] + 1; next.add(v); }
20            }
21        if (best != Integer.MAX_VALUE) return best;               // the whole layer is done: the smallest total is exact
22        if (fromS) fs = next; else ft = next;
23    }
24    return -1;
25}

Bidirectional BFS: two searches that meet in the middle

Interactive · edit the input

undirected graph · 8 vertices · 9 edges

s:0

t:0

Reached from the sourceReached from the targetWhere the searches touch

frontier from the source

frontier from the target

Setup

Search from both ends at once. If the answer has length d, each search only needs to reach about d / 2 layers, and a graph with many branches has far fewer vertices in two small balls than in one big one. Each round expands a whole layer of the smaller frontier.

Step 1 / 7

Java

1int bidirectional(List<List<Integer>> g, int s, int t) {   // fewest edges, or -1
2    if (s == t) return 0;
3    int n = g.size(); int[] ds = new int[n], dt = new int[n];
4    Arrays.fill(ds, -1); Arrays.fill(dt, -1);
5    ds[s] = 0; dt[t] = 0;
6    List<Integer> fs = List.of(s), ft = List.of(t);
7    while (!fs.isEmpty() && !ft.isEmpty()) {
8        boolean fromS = fs.size() <= ft.size();   // expand the smaller frontier
9        List<Integer> frontier = fromS ? fs : ft;
10        int[] mine = fromS ? ds : dt, other = fromS ? dt : ds;
11        List<Integer> next = new ArrayList<>(); int best = Integer.MAX_VALUE;
12        for (int u : frontier)
13            for (int v : g.get(u)) {
14                if (other[v] != -1) best = Math.min(best, mine[u] + 1 + other[v]);   // the two searches touch
15                if (mine[v] == -1) { mine[v] = mine[u] + 1; next.add(v); }
16            }
17        if (best != Integer.MAX_VALUE) return best;   // finish the whole layer, then take the smallest
18        if (fromS) fs = next; else ft = next;
19    }
20    return -1;
21}

Live state

0 vertices expanded

source

target

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L5	source=0 target=7	Search from both ends at once. If the answer has length d, each search only needs to reach about d / 2 layers, and a graph with many branches has far fewer vertices in two small balls than in one big one. Each round expands a whole layer of the smaller frontier.
2	L9	side=source layer=1 vertices expanded=1	Expand the whole source layer at distance 0 (it was the smaller frontier, 1 vs 1). No contact yet.
3	L9	side=target layer=1 vertices expanded=2	Expand the whole target layer at distance 0 (it was the smaller frontier, 1 vs 2). No contact yet.
4	L9	side=source layer=2 vertices expanded=4	Expand the whole source layer at distance 1 (it was the smaller frontier, 2 vs 2). No contact yet.
5	L9	side=source layer=3 vertices expanded=5	Expand the whole source layer at distance 2 (it was the smaller frontier, 1 vs 2). No contact yet.
6	L9	side=source layer=4 vertices expanded=6	Expand the whole source layer at distance 3 (it was the smaller frontier, 1 vs 2). The searches touch: the best total is 5.
7	L17	return=5 vertices expanded=6	Shortest distance 5, found after expanding 6 vertices. The whole layer is finished before stopping, so the smallest of the touching totals is exact.

35.09.2

Bidirectional Dijkstra

Bidirectional Dijkstra runs a forward search on the graph and a backward search on the reversed graph, each with its own priority queue. Whenever an edge reaches a vertex labelled by the other side, update best = min(best, forward + w + backward). The searches may touch long before the answer is certain.

**Stop** when the sum of the two smallest queue keys is at least best: any path not yet found must cost at least that sum. Stopping at the first touch is a common mistake and gives wrong answers. Both searches need non-negative weights.

Java

1static long bidirectionalDijkstra(int n, List<int[]>[] fwd, List<int[]>[] bwd, int s, int t) {   // weights >= 0; Long.MAX_VALUE if unreachable
2    long INF = Long.MAX_VALUE / 2;
3    List<int[]>[][] graph = new List[][]{fwd, bwd};
4    long[][] dist = new long[2][n];
5    for (long[] d : dist) Arrays.fill(d, INF);
6    dist[0][s] = 0;
7    dist[1][t] = 0;
8    List<PriorityQueue<long[]>> pq = new ArrayList<>();
9    for (int side = 0; side < 2; side++) pq.add(new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0])));
10    pq.get(0).add(new long[]{0, s});
11    pq.get(1).add(new long[]{0, t});
12    long best = s == t ? 0 : INF;
13    while (true) {
14        long topF = pq.get(0).isEmpty() ? INF : pq.get(0).peek()[0];
15        long topB = pq.get(1).isEmpty() ? INF : pq.get(1).peek()[0];
16        if (topF + topB >= best || (topF == INF && topB == INF)) break;   // no unfinished route can still beat best
17        int side = topF <= topB ? 0 : 1;
18        long[] top = pq.get(side).poll();
19        int u = (int) top[1];
20        if (top[0] > dist[side][u]) continue;
21        for (int[] e : graph[side][u]) {
22            if (dist[side][u] + e[1] < dist[side][e[0]]) {
23                dist[side][e[0]] = dist[side][u] + e[1];
24                pq.get(side).add(new long[]{dist[side][e[0]], e[0]});
25            }
26            if (dist[1 - side][e[0]] < INF) best = Math.min(best, dist[side][u] + e[1] + dist[1 - side][e[0]]);   // touch through this edge
27        }
28    }
29    return best >= INF ? Long.MAX_VALUE : best;
30}

35.09.3

K shortest paths overview

The **k shortest walks** (repeated vertices allowed) from s to t come from Dijkstra with one change: let each vertex be popped up to k times instead of once. The j-th time t is popped gives the j-th cheapest walk. The cost is O(k · m log(k · m)) pushes.

**Yen's algorithm** finds the k shortest *simple* paths (no repeated vertex), which is usually what people mean. It takes the best path found so far, and for each prefix of it forbids the edges already used there and searches for the best detour; the cheapest detours become the next candidates. It runs a shortest-path search about k · n times.

Java

1static List<Long> kShortestWalks(int n, List<int[]>[] adj, int s, int t, int k) {   // costs of the k cheapest walks s -> t, weights > 0
2    int[] pops = new int[n];
3    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));   // {cost, vertex}
4    pq.add(new long[]{0, s});
5    List<Long> costs = new ArrayList<>();
6    while (!pq.isEmpty() && costs.size() < k) {
7        long[] top = pq.poll();
8        int u = (int) top[1];
9        if (pops[u] == k) continue;                                // only the k cheapest arrivals at u can matter
10        pops[u]++;
11        if (u == t) costs.add(top[0]);
12        for (int[] e : adj[u]) pq.add(new long[]{top[0] + e[1], e[0]});
13    }
14    return costs;
15}

35.09.4

Multicriteria shortest path intro

When an edge has two costs, say price and time, there is usually no single best path, only a set of paths where none is better than another in both costs. A path *dominates* another if it is no worse in both and the costs are not identical. The non-dominated set is the **Pareto front**.

The standard method is label-setting: keep for each vertex a list of non-dominated {cost, time} labels, expand labels in order of the first cost, and drop any label dominated by one already at that vertex. The front can be exponentially large in the worst case, so real systems also limit or combine the criteria, for example with a weighted sum.

Java

1static List<long[]> paretoFront(int n, List<int[]>[] adj, int s, int t) {   // adj[u] = {v, cost, time}, both > 0; the non-dominated {cost, time} pairs at t
2    List<List<long[]>> labels = new ArrayList<>();
3    for (int i = 0; i < n; i++) labels.add(new ArrayList<>());
4    PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));   // {cost, time, vertex}
5    pq.add(new long[]{0, 0, s});
6    while (!pq.isEmpty()) {
7        long[] cur = pq.poll();
8        int u = (int) cur[2];
9        boolean dominated = false;
10        for (long[] l : labels.get(u)) if (l[0] <= cur[0] && l[1] <= cur[1]) { dominated = true; break; }
11        if (dominated) continue;                                    // an earlier label is at least as good in both
12        labels.get(u).add(new long[]{cur[0], cur[1]});
13        for (int[] e : adj[u]) pq.add(new long[]{cur[0] + e[1], cur[1] + e[2], e[0]});
14    }
15    return labels.get(t);
16}

Practice ladder

Now try it yourself

Easy

Find if Path Exists in Graph

Medium

Word Ladder
Open the Lock
Network Delay Time

Advanced

Word Ladder II
Minimum Genetic Mutation
Cheapest Flights Within K Stops

Key takeaways

Bidirectional BFS expands the smaller frontier a whole layer at a time and stops after the layer in which the searches touch.
Bidirectional Dijkstra stops when the two smallest keys add up to at least the best total found, not at the first touch.
Letting each vertex be popped k times gives the k cheapest walks; Yen's algorithm gives simple paths.
With two costs, keep the non-dominated labels (the Pareto front); it can be large.