Two-Phase Bfs For “Exactly K Edges” Shortest-Path Counting

I tripped over a surprisingly nasty bug while building a little “route planner” for a grid. The UI asked for: “minimum travel time” and also showed how many shortest routes exist. Then the spec added a twist:

Only routes that use exactly K edges should count.

That detail wrecked my usual approach (“run shortest path, then count paths”), because the “fewest weight” solution and the “exactly K hops” constraint don’t line up in a simple way. I ended up using a two-phase trick that kept both constraints honest.

Below is the niche algorithm I used, with working code: two-phase BFS + hop-layer DP for shortest paths in an unweighted graph, where path length means number of edges and we require exactly K edges.

---

The core problem (in concrete terms)

Given an unweighted directed graph:

• Every edge has weight 1 (so “shortest” means “fewest edges”).
• Find:
  1. d = shortest distance from S to T in edges
  2. count = number of distinct shortest paths from S to T that use exactly K edges.

In an unweighted graph, any shortest path must have length exactly d. So when K != d, the answer must be 0.

However, in practice the interesting case is when you want to count paths from S to any target that are simultaneously:

• “shortest to each node from S”, and
• “shortest-to-target overall”, and
• “exactly K edges”.

The simplest consistent interpretation becomes:

• Count paths to T that:
  • reach T with total path length exactly K, and
  • are globally shortest among all S→T routes (so K must equal the shortest length).

That’s what the algorithm below computes cleanly.

---

Key idea: two-phase BFS + layer-restricted counting

Definitions

• BFS (Breadth-First Search) computes shortest distances in an unweighted graph.
• I build distance layers: layer i contains nodes at distance i from S.
• Then I do DP (dynamic programming) over layers while only allowing edges that respect shortest-distance progression.

Phase 1: BFS from S to compute distances

Run BFS from S to compute dist[u] = shortest edges from S to u.

If T is unreachable, answer is 0.

Let d = dist[T]. If K != d, answer is 0.

Phase 2: Count ways that follow shortest-distance edges

Now I count the number of ways to reach each node using exactly the correct number of edges without violating shortestness.

For an unweighted shortest path, edges along the path satisfy:

• If u -> v is used, then dist[v] == dist[u] + 1.

So I only accumulate DP transitions across edges that go from layer i to layer i+1.

---

Working code (Python)

This implementation handles directed graphs, multiple edges, and large graphs efficiently.

from collections import deque, defaultdict

def count_shortest_paths_exact_k_edges(n, edges, S, T, K):
    """
    n: number of nodes (0..n-1)
    edges: list of (u, v) directed edges
    S, T: source and target nodes
    K: required number of edges in the path

    Returns: number of shortest S->T paths that use exactly K edges.
             In an unweighted graph, shortest path length is unique = dist[T],
             so answer is 0 unless K == dist[T].
    """
    g = [[] for _ in range(n)]
    for u, v in edges:
        g[u].append(v)

    # Phase 1: BFS from S to compute shortest distances
    INF = -1
    dist = [INF] * n
    q = deque([S])
    dist[S] = 0

    while q:
        u = q.popleft()
        for v in g[u]:
            if dist[v] == INF:
                dist[v] = dist[u] + 1
                q.append(v)

    d = dist[T]
    if d == INF:
        return 0
    if K != d:
        return 0

    # Phase 2: DP counting number of shortest paths by layer
    # ways[u] = number of shortest ways to reach u using dist[u] edges
    ways = [0] * n
    ways[S] = 1

    # We process nodes in increasing distance.
    # To keep it simple and fast, bucket nodes by distance.
    buckets = [[] for _ in range(d + 1)]
    for u in range(n):
        if 0 <= dist[u] <= d:
            buckets[dist[u]].append(u)

    for layer in range(d):
        for u in buckets[layer]:
            if ways[u] == 0:
                continue
            # Only shortest edges go to next layer
            for v in g[u]:
                if dist[v] == dist[u] + 1:
                    ways[v] += ways[u]

    return ways[T]


if __name__ == "__main__":
    # Example directed graph
    # S=0, T=4
    edges = [
        (0, 1), (0, 2),
        (1, 3), (2, 3),
        (3, 4),
        # Extra edges that could create longer paths but shouldn't affect "shortest"
        (1, 2),
        (2, 1),
    ]

    n = 5
    S, T = 0, 4

    for K in range(1, 6):
        ans = count_shortest_paths_exact_k_edges(n, edges, S, T, K)
        print(f"K={K} -> {ans}")

What happens when I run it

For this graph:

• Shortest path length from 0 to 4 is 3 edges:
  • 0 → 1 → 3 → 4
  • 0 → 2 → 3 → 4
• So there are 2 shortest routes.

The output should be:

• K=3 -> 2
• All other K values -> 0

Because in an unweighted graph, any shortest path to T must use exactly dist[T] edges.

---

Why the layer-restricted DP is correct

A tempting (wrong) approach would be:

1. Count all paths of length K
2. Then try to filter by shortestness afterward

That gets expensive and forces you to keep extra state.

The two-phase method is correct because:

• Phase 1 guarantees dist[u] is the minimum edge count from S.
• Any shortest path to a node v must end with an edge from some u at distance dist[v]-1.
• Therefore, the DP transition u -> v is valid iff dist[v] = dist[u] + 1.
• Processing layers in order ensures every partial count contributes only to shortest paths of the correct length.

---

Edge cases I hit (and how the code handles them)

1) Unreachable target

If T is unreachable from S, dist[T] remains -1, and the function returns 0.

2) K doesn’t match shortest distance

Because every shortest path must have length dist[T], the answer is 0 when K != dist[T].

3) Multiple shortest routes merging

When two different shortest prefixes land on the same node in the same layer, their counts add up naturally via ways[v] += ways[u].

---

Complexity

• BFS: O(n + m) where m is number of edges.
• DP: also O(n + m) because each edge is checked at most once during layer processing.

Memory: O(n + m) for adjacency lists and arrays.

---

Conclusion

I learned that adding an “exactly K edges” constraint to shortest-path counting doesn’t work with a naive single-pass approach. The reliable pattern in an unweighted directed graph is: BFS to lock in the shortest distance layers, then DP across only those edges that advance exactly one layer. In this setup, the “exactly K edges” requirement becomes a simple—and correct—gate: the answer is non-zero only when K equals the BFS distance to the target, and the DP then counts every shortest route that respects that layer structure.