The k shortest simple (loopless) paths between two nodes, in
nondecreasing hop count: the individual routes a host lists as
"path 3 of 12: A -knows- B -cites- C", which allShortestPaths
(a union subgraph plus a count) cannot give back.
Algorithm: Yen's, with BFS as the shortest-path subroutine since
every hop weighs one. Chosen over enumerating only the
shortest-LENGTH routes because a listing that stops at the
shortest length answers "which routes tie for shortest" but not
"what is the next-best route", and the latter is what a path
finder shows once the first route is ruled out. Each returned path
costs at most L bounded BFS runs, where L is its hop count, so the
whole call is O(k * L * (n + m)) on a graph of n nodes and m
edges; maxHops caps L and every spur search, which is what keeps
a search on a 100,000-edge index from running to exhaustion.
Deterministic: BFS walks edges in the graph's own iteration order,
and among candidates of equal length the one discovered first
wins, so the same graph and options list the same paths in the
same order every call. Parallel edges yield distinct paths (same
nodeIds, different edgeIds), matching how allShortestPaths counts
them. Fewer than k paths exist: the array is shorter. Disconnected
or missing endpoints (a node hasNode does not report, the same
rule as findShortestPath): empty array. Source equals target on an
existing node: the one trivial path, [{ nodeIds: [id], edgeIds: [] }].
The k shortest simple (loopless) paths between two nodes, in nondecreasing hop count: the individual routes a host lists as "path 3 of 12: A -knows- B -cites- C", which allShortestPaths (a union subgraph plus a count) cannot give back.
Algorithm: Yen's, with BFS as the shortest-path subroutine since every hop weighs one. Chosen over enumerating only the shortest-LENGTH routes because a listing that stops at the shortest length answers "which routes tie for shortest" but not "what is the next-best route", and the latter is what a path finder shows once the first route is ruled out. Each returned path costs at most L bounded BFS runs, where L is its hop count, so the whole call is O(k * L * (n + m)) on a graph of n nodes and m edges;
maxHopscaps L and every spur search, which is what keeps a search on a 100,000-edge index from running to exhaustion.Deterministic: BFS walks edges in the graph's own iteration order, and among candidates of equal length the one discovered first wins, so the same graph and options list the same paths in the same order every call. Parallel edges yield distinct paths (same nodeIds, different edgeIds), matching how allShortestPaths counts them. Fewer than k paths exist: the array is shorter. Disconnected or missing endpoints (a node
hasNodedoes not report, the same rule as findShortestPath): empty array. Source equals target on an existing node: the one trivial path,[{ nodeIds: [id], edgeIds: [] }].