Main Content

Find all shortest paths in graph

`[`

* dist*] =
graphallshortestpaths(

`G`

[

`dist`

`G`

`DirectedValue`

[

`dist`

`G`

`WeightsValue`

`G` | N-by-N sparse matrix that represents a graph. Nonzero entries
in matrix represent the weights of the
edges.`G` |

`DirectedValue` | Property that indicates whether the graph is directed or undirected.
Enter `false` for an undirected graph. This results
in the upper triangle of the sparse matrix being ignored. Default
is `true` . |

`WeightsValue` | Column vector that specifies custom weights for the edges in
matrix . It must have one entry for every
nonzero value (edge) in matrix `G` . The order
of the custom weights in the vector must match the order of the nonzero
values in matrix `G` when it is traversed
column-wise. This property lets you use zero-valued weights. By default, `G` `graphallshortestpaths` gets
weight information from the nonzero entries in matrix .`G` |

**Tip**

For introductory information on graph theory functions, see Graph Theory Functions.

`[`

finds
the shortest paths between every pair of nodes in the graph represented
by matrix * dist*] =
graphallshortestpaths(

`G`

`G`

`G`

`G`

Output * dist* is an N-by-N matrix where

`dist`

(S,T)

is
the distance of the shortest path from source node `S`

to
target node `T`

. Elements in the diagonal of this
matrix are always `0`

, indicating the source node
and target node are the same. A `0`

not in the diagonal
indicates that the distance between the source node and target node
is `0`

. An `Inf`

indicates there
is no path between the source node and the target node. Johnson's algorithm has a time complexity of `O(N*log(N)+N*E)`

,
where `N`

and `E`

are the number
of nodes and edges respectively.

`[...] = graphallshortestpaths (`

calls * G*,
'

`PropertyName`

`PropertyValue`

`graphallshortestpaths`

with
optional properties that use property name/property value pairs. You
can specify one or more properties in any order. Each `PropertyName`

```
[
```

indicates whether the graph is directed
or undirected. Set * dist*] =
graphallshortestpaths(

`G`

`DirectedValue`

`DirectedValue`

`false`

for
an undirected graph. This results in the upper triangle of the sparse
matrix being ignored. Default is `true`

.`[`

lets
you specify custom weights for the edges. * dist*] = graphallshortestpaths(

`G`

`WeightsValue`

`WeightsValue`

`G`

`G`

`graphallshortestpaths`

gets
weight information from the nonzero entries in matrix `G`

Example 31. Finding All Shortest Paths in a Directed Graph

Create and view a directed graph with 6 nodes and 11 edges.

W = [.41 .99 .51 .32 .15 .45 .38 .32 .36 .29 .21]; DG = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W) DG = (4,1) 0.4500 (6,2) 0.4100 (2,3) 0.5100 (5,3) 0.3200 (6,3) 0.2900 (3,4) 0.1500 (5,4) 0.3600 (1,5) 0.2100 (2,5) 0.3200 (1,6) 0.9900 (4,6) 0.3800 view(biograph(DG,[],'ShowWeights','on'))

Find all the shortest paths between every pair of nodes in the directed graph.

graphallshortestpaths(DG) ans = 0 1.3600 0.5300 0.5700 0.2100 0.9500 1.1100 0 0.5100 0.6600 0.3200 1.0400 0.6000 0.9400 0 0.1500 0.8100 0.5300 0.4500 0.7900 0.6700 0 0.6600 0.3800 0.8100 1.1500 0.3200 0.3600 0 0.7400 0.8900 0.4100 0.2900 0.4400 0.7300 0

The resulting matrix shows the shortest path from node 1 (first row) to node 6 (sixth column) is 0.95. You can see this in the graph by tracing the path from node 1 to node 5 to node 4 to node 6 (0.21 + 0.36 + 0.38 = 0.95).

Example 32. Finding All Shortest Paths in an Undirected Graph

Create and view an undirected graph with 6 nodes and 11 edges.

UG = tril(DG + DG') UG = (4,1) 0.4500 (5,1) 0.2100 (6,1) 0.9900 (3,2) 0.5100 (5,2) 0.3200 (6,2) 0.4100 (4,3) 0.1500 (5,3) 0.3200 (6,3) 0.2900 (5,4) 0.3600 (6,4) 0.3800 view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'))

Find all the shortest paths between every pair of nodes in the undirected graph.

`graphallshortestpaths(UG,'directed',false) ans = 0 0.5300 0.5300 0.4500 0.2100 0.8300 0.5300 0 0.5100 0.6600 0.3200 0.7000 0.5300 0.5100 0 0.1500 0.3200 0.5300 0.4500 0.6600 0.1500 0 0.3600 0.3800 0.2100 0.3200 0.3200 0.3600 0 0.7400 0.8300 0.7000 0.5300 0.3800 0.7400 0`

The resulting matrix is symmetrical because it represents an undirected graph. It shows the shortest path from node 1 (first row) to node 6 (sixth column) is 0.83. You can see this in the graph by tracing the path from node 1 to node 4 to node 6 (0.45 + 0. 38 = 0.83). Because

`UG`

is an undirected graph, we can use the edge between node 1 and node 4, which we could not do in the directed graph`DG`

.

[1] Johnson, D.B. (1977). Efficient algorithms
for shortest paths in sparse networks. Journal of the ACM *24(1)*,
1-13.

[2] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). The Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).

`allshortestpaths`

| `graphconncomp`

| `graphisdag`

| `graphisomorphism`

| `graphisspantree`

| `graphmaxflow`

| `graphminspantree`

| `graphpred2path`

| `graphshortestpath`

| `graphtopoorder`

| `graphtraverse`