Fewest-Edge Distance Between Two Nodes in a Directed Acyclic Graph

This came as a follow-up to ordering the nodes of a dependency graph. You are given a directed acyclic graph with n nodes labeled 0 to n - 1, a list of directed edges where [u, v] is an edge from u to v, and two nodes source and target. Return the distance from source to target: the smallest number of edges on a path that starts at source, follows edges in their direction, and ends at target.

Function Signature

def dag_distance(n: int, edges: list[list[int]], source: int, target: int) -> int:

Rules

• An edge [u, v] can be followed only from u to v, never backwards.
• If source == target, the distance is 0.
• If no directed path from source to target exists, return -1.
• An edge may be listed more than once; repeats do not change the answer.

Constraints

• 1 <= n <= 10^5
• 0 <= len(edges) <= 2 * 10^5
• 0 <= u, v, source, target < n
• the graph has no directed cycles and no self-loops

Examples

Example 1

Input: n = 6, edges = [[0, 1], [1, 2], [2, 5], [0, 3], [3, 5], [1, 4]], source = 0, target = 5
Output: 2

The path 0 -> 3 -> 5 uses two edges; the other path, 0 -> 1 -> 2 -> 5, uses three.

Example 2

Input: n = 6, edges = [[0, 1], [1, 2], [2, 5], [0, 3], [3, 5], [1, 4]], source = 3, target = 2
Output: -1

From node 3 the only edge leads to node 5, which has no outgoing edges, so node 2 cannot be reached. The edge [1, 2] cannot be used because node 1 is never reached from node 3.

Example 3

Input: n = 3, edges = [[0, 1]], source = 2, target = 2
Output: 0

The source is the target, so no edge is needed.