`shortestpath`

Shortest path between two nodes.

Category: Mathematics > Graph and Network Algorithms

Syntax

p = shortestpath(G, s, t)

Returns the nodes along a shortest path from s to t.

[p, d] = shortestpath(G, s, t)

Also returns the length of the path.

Description

Without weights each edge has length 1 and the path has the fewest edges. With weights it minimizes the total weight, so a longer path in edges can win over a shorter one. In a digraph the path must follow edge directions.

When several paths tie, one of them is returned. For distances from one node to every other, distances or shortestpathtree is cheaper than calling shortestpath repeatedly.

Input arguments

G: A graph or digraph. Edge weights, if present, are the edge lengths and must not be negative.
s, t: Start and end nodes, as indices or names.

Output arguments

p: Row vector of nodes from s to t, or a cell array of names for a named graph. Empty if t cannot be reached.
d: Total length of the path. Inf when there is no path.

Example

Weighted route

D = digraph([1 1 2 3 4], [2 3 4 4 5], [1 4 2 1 3]);
[p, d] = shortestpath(D, 1, 5)
shortestpath(D, 5, 1)

Output

p = 1×4

     1     2     4     5
d = 6
ans = 1×0 empty double row vector

shortestpath