FindShortestPath

A shortest path from u to v, respecting edge direction (BFS, unweighted).

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageFindShortestPath✓↗

FindShortestPath(g, u, v)the vertices of one shortest $u \to v$ path, both ends included; the empty list if $v$ is unreachable from $u$.

Typed signatures

Type	Package	Applies
(value, any, any) -> list<any>	combinatorics	always

Domain: Collections

Details

• A directed edge is only traversable forward; an undirected edge, either way.
• Weighted (g carries EdgeWeight): the path minimizing summed edge weight (Dijkstra), not the fewest hops — same as Wolfram, which reads EdgeWeight automatically when present. Requires every weight to be non-negative; a negative weight leaves the call unevaluated rather than guess (Dijkstra doesn't support them — Wolfram itself switches algorithm in that case, out of scope here).

Examples

1 more kept as data, checked against the oracles

Basic #

live ↗

In$\mathrm{FindShortestPath}(\mathrm{PathGraph}(5), 1, 5)$Out$\bigl\lbrack1, 2, 3, 4, 5\bigr\rbrack$

Directed edges block the way back

live ↗

In$\mathrm{FindShortestPath}(\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4\bigr\rbrack, \bigl\lbrack\mathrm{DirectedEdge}(1, 2), \mathrm{DirectedEdge}(2, 3), \mathrm{UndirectedEdge}(3, 4)\bigr\rbrack), 4, 1)$Out$\bigl\lbrack\bigr\rbrack$

With EdgeWeight given, Dijkstra picks the three cheap hops (total 3) over the direct but expensive edge (10) — plain hop-count BFS would take the direct edge instead

live ↗

In$\mathrm{FindShortestPath}(\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(2, 3), \mathrm{UndirectedEdge}(3, 4), \mathrm{UndirectedEdge}(1, 4)\bigr\rbrack, \operatorname{KeyValuePair}(\mathrm{EdgeWeight}, \bigl\lbrack1, 1, 1, 10\bigr\rbrack)), 1, 4)$Out$\bigl\lbrack1, 2, 3, 4\bigr\rbrack$

About

Examples	4
Checked against	Wolfram Language 3 agree
Crosswalk	Wolfram Language

See also: GraphDistance, GraphDistanceMatrix, Graph