`distances`

Shortest-path distances between nodes.

Category: Mathematics > Graph and Network Algorithms

Syntax

D = distances(G)

Returns the distance between every pair of nodes.

D = distances(G, s)

Distances from the nodes s to all nodes.

D = distances(G, s, t)

Distances from the nodes s to the nodes t.

Description

For an undirected graph the full matrix is symmetric with zeros on the diagonal. For a digraph, D(i,j) and D(j,i) can differ, and one of them can be Inf.

Use distances when you need many distances at once; shortestpath returns a single path together with its length.

Input arguments

G: A graph or digraph. Edge weights, if present, are the edge lengths; otherwise each edge has length 1.
s, t: Source and target nodes, as indices or names.

Output arguments

D: Matrix with D(i,j) the length of the shortest path from the i-th source to the j-th target. Inf marks an unreachable pair.

Example

All pairs in a small digraph

D = digraph([1 1 2 3 4], [2 3 4 4 5], [1 4 2 1 3]);
distances(D)

Output

ans = 5×5

     0     1     4     3     6
   Inf     0   Inf     2     5
   Inf   Inf     0     1     4
   Inf   Inf   Inf     0     3
   Inf   Inf   Inf   Inf     0

distances