Skip to content

FindShortestPath

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

FindShortestPath[g,s,t] gives a shortest path from s to t as a list of vertices ({} if none).

Examples

No verified examples yet for this function.

Algorithm

shortestpath.c - FindShortestPath[g,s,t] and GraphDistance[g,s,t].

Unweighted breadth-first search over the successor adjacency (out[]): for a directed graph this follows edge direction; for an undirected graph out[] is symmetric, so it is an ordinary shortest path. Wolfram's naming split is kept: FindShortestPath returns the vertex path, GraphDistance the length.

Unreachable target: FindShortestPath -> {} (empty list), GraphDistance -> Infinity.

Memory (SPEC section 4): returns freshly-allocated results; frees res.

Implementation notes

Attributes: Protected.

References