Find the Shortest Path Between Two Vertices

Given an unweighted directed graph and two vertices src and dst, find a shortest path from src to dst: one with the fewest edges. Return null (no list) if dst can't be reached.

Example

graph LR
    0 --> 1
    0 --> 2
    0 --> 5
    1 --> 3
    2 --> 3
    3 --> 4
    5 --> 4

Text

shortest(0, 4) = [0, 5, 4]   (2 edges)
The other paths, 0 -> 1 -> 3 -> 4 and 0 -> 2 -> 3 -> 4, use 3 edges.
shortest(4, 0) = null

Brute force: try every simple path

Explore every path from src with backtracking, recording the length whenever dst is reached, and keep the minimum.

Java

import java.util.List;

public class Main {
    // best[0] holds the shortest length found so far, or -1 if none
    static void explore(List<List<Integer>> adj, int v, int dst, int depth, boolean[] onPath, int[] best) {
        if (v == dst) {
            if (best[0] == -1 || depth < best[0]) best[0] = depth;
            return;
        }
        onPath[v] = true;
        for (int w : adj.get(v)) {
            if (!onPath[w]) {
                explore(adj, w, dst, depth + 1, onPath, best);
            }
        }
        onPath[v] = false;
    }

    static int shortestLen(List<List<Integer>> adj, int src, int dst) {
        int[] best = {-1};
        explore(adj, src, dst, 0, new boolean[adj.size()], best);
        return best[0];
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = List.of(
            List.of(1, 2, 5), List.of(3), List.of(3), List.of(4), List.of(), List.of(4));
        System.out.println(shortestLen(adj, 0, 4) + " " + shortestLen(adj, 4, 0));
    }
}

Output

2 -1

The brute-force method returns the length, or -1 when there is no path. Time: exponential in the worst case, since the number of simple paths can be exponential. Space: O(V).

Optimal: BFS with a parent array

BFS visits vertices in order of their distance from src: first every vertex 1 edge away, then every vertex 2 edges away, and so on. So the first time BFS reaches a vertex, it has reached it by a shortest path.

To return the path itself, record each vertex's parent: the vertex it was discovered from. When dst is reached, follow the parents back from dst to src and reverse the result.

Walkthrough of shortest(0, 4):

take	newly discovered (parent)	queue after
0	1 (0), 2 (0), 5 (0)	[1, 2, 5]
1	3 (1)	[2, 5, 3]
2	none (3 already discovered)	[5, 3]
5	4 (5)	[3, 4]
3	none (4 already discovered)	[4]
4	this is `dst`	stop

Following parents back from 4 gives 4 → 5 → 0, which reversed is [0, 5, 4].

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;

public class Main {
    // Returns null when dst cannot be reached.
    static List<Integer> shortestPath(List<List<Integer>> adj, int src, int dst) {
        int[] parent = new int[adj.size()];
        java.util.Arrays.fill(parent, -1);
        boolean[] visited = new boolean[adj.size()];
        visited[src] = true;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(src);

        while (!queue.isEmpty()) {
            int v = queue.poll();
            if (v == dst) {
                List<Integer> path = new ArrayList<>();
                for (int cur = dst; cur != -1; cur = parent[cur]) {
                    path.add(cur);
                }
                Collections.reverse(path);
                return path;
            }
            for (int w : adj.get(v)) {
                if (!visited[w]) {
                    visited[w] = true;
                    parent[w] = v;
                    queue.add(w);
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = List.of(
            List.of(1, 2, 5), List.of(3), List.of(3), List.of(4), List.of(), List.of(4));
        List<Integer> path = shortestPath(adj, 0, 4);
        System.out.println(path + ", edges = " + (path.size() - 1));
        System.out.println(shortestPath(adj, 4, 0));
        System.out.println(shortestPath(adj, 2, 2));
    }
}

Output

[0, 5, 4], edges = 2
null
[2]

Time: O(V + E). Space: O(V) for the parent array, the visited flags, and the queue.

parent[src] stays -1, which is how the path rebuild knows it has reached the start. queue is an ArrayDeque used through the Queue interface: add at the back, poll from the front.

Distances to every vertex

If you need the distance from src to every vertex, store dist[w] = dist[v] + 1 when w is discovered, instead of stopping at dst:

Java

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

public class Main {
    // dist[v] is -1 when v is unreachable from src
    static int[] distances(List<List<Integer>> adj, int src) {
        int[] dist = new int[adj.size()];
        Arrays.fill(dist, -1);
        dist[src] = 0;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(src);
        while (!queue.isEmpty()) {
            int v = queue.poll();
            for (int w : adj.get(v)) {
                if (dist[w] == -1) {
                    dist[w] = dist[v] + 1;
                    queue.add(w);
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = List.of(
            List.of(1, 2, 5), List.of(3), List.of(3), List.of(4), List.of(), List.of(4));
        System.out.println(Arrays.toString(distances(adj, 0)));
    }
}

Output

[0, 1, 1, 2, 2, 1]

Here dist[w] == -1 also serves as the visited check, and -1 marks a vertex that cannot be reached.

Weighted graphs

When edges have different costs, BFS no longer gives the cheapest path, because a path with more edges can cost less. For non-negative weights, use Dijkstra's algorithm, which replaces the queue with a min-heap (PriorityQueue ordered by distance with Comparator.comparingLong) so that the closest unfinished vertex is always processed next. For weights of only 0 and 1, a deque works: use an ArrayDeque and call addFirst for 0-weight edges and addLast for 1-weight edges.