`shortestpathtree`

Tree of shortest paths from one source node.

Category: Mathematics > Graph and Network Algorithms

Syntax

T = shortestpathtree(G, s)

Returns the tree of shortest paths from s to all reachable nodes.

Description

The shortest paths from one source never need to split and rejoin, so together they form a tree rooted at s. Following the tree edges from s to any node reproduces shortestpath(G, s, node).

This is the structure computed by Dijkstra's algorithm.

Input arguments

G: A graph or digraph with non-negative weights.
s: Source node, as index or name.

Output arguments

T: A graph with the nodes of G and, for each reachable node other than s, the one edge by which its shortest path arrives. Edge weights are kept.

Example

Tree from node 1

D = digraph([1 1 2 3 4], [2 3 4 4 5], [1 4 2 1 3]);
T = shortestpathtree(D, 1);
disp(T.Edges)
numedges(T)

Output

    EndNodes    Weight
    ________    ______

     1    2       1   
     1    3       4   
     2    4       2   
     4    5       3   
ans = 4

Notes

Restricting the tree to chosen targets (shortestpathtree(G, s, t)) and the 'OutputForm' option are accepted but ignored: the full tree is returned.

shortestpathtree