[ library(graph_algorithms) | Reference Manual | Alphabetic Index ]

single_pair_shortest_path(+Graph, +DistanceArg, +SourceNode, +SinkNode, -Path)

Computes one shortest path from a source to a sink node
Graph
a graph structure
DistanceArg
which argument of EdgeData to use as distance: integer
SourceNode
source node number (integer)
SinkNode
sink node number (integer)
Path
Length-EdgeList structure

Description

Computes one shortest path from SourceNode to SinkNode. Fails if there is no path at all. In case of multiple shortest paths with the same length, an arbitrary one is returned.

DistanceArg refers to the graph's EdgeData information that was specified when the graph was constructed. If EdgeData is a simple number, then DistanceArg should be 0 and EdgeData will be taken as the length of the edge. If EdgeData is a compound data structure, DistanceArg should be a number between 1 and the arity of that structure and determines which argument of the EdgeData structure will be interpreted as the edge's length. Important: the distance information in EdgeData must be a non-negative number, and the numeric type (integer, float, etc) must be the same in all edges.

If DistanceArg is given as -1, then any EdgeData is ignored and the length of every edge is assumed to be equal to 1.

The shortest path is returned as a Length-EdgeList structure where Length is the length of the shortest path and EdgeList is that path (or one of them) in reverse order, i.e. starting with the edge reaching SinkNode and ending with the edge starting from SourceNode.

Modes and Determinism

Fail Conditions

There is no path from SourceNode to SinkNode

Examples

    ?- sample_graph(G), single_pair_shortest_path(G, 0, 1, 3, P).
    P = 2 - [e(2, 3, 1), e(1, 2, 1)]
    

See Also

shortest_paths / 4, all_short_paths_as_edges / 6, all_short_paths_as_graph / 6, single_pair_short_path / 6, single_pair_all_short_paths_as_graph / 7, possible_path / 7