Method ADT.Relation.Binary()->find_shortest_path()
- Method find_shortest_path
array
find_shortest_path(mixed
from
,mixed
to
,void
|multiset
avoiding
)- Description
Assuming the relation's domain and range sets are equal, and that the relation xRy means "there is a path from node x to node y", find_shortest_path attempts to find a path with a minimum number of steps from one given node to another. The path is returned as an array of nodes (including the starting and ending node), or 0 if no path was found. If several equally short paths exist, one of them will be chosen pseudorandomly.
Trying to find a path from a node to itself will always succeed, returning an array of one element: the node itself. (Or in other words, a path with no steps, only a starting/ending point).
The argument
avoiding
is either 0 (or omitted), or a multiset of nodes that must not be part of the path.