# graphallshortestpaths

(To be removed) Find all shortest paths in graph

`graphallshortestpaths` will be removed in a future release. Use `distances` instead.

## Syntax

```[dist] = graphallshortestpaths(G) [dist] = graphallshortestpaths(G, ...'Directed', DirectedValue, ...) [dist] = graphallshortestpaths(G, ...'Weights', WeightsValue, ...) ```

## Arguments

 `G` N-by-N adjacency matrix that represents a graph. Nonzero entries in matrix `G` represent the weights of the edges. `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 matrix being ignored. Default is `true`. `WeightsValue` Column vector that specifies custom weights for the edges in matrix `G`. 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, `graphallshortestpaths` gets weight information from the nonzero entries in matrix `G`.

## Description

Tip

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

```[dist] = graphallshortestpaths(G)``` finds the shortest paths between every pair of nodes in the graph represented by matrix `G`, using Johnson's algorithm. Input `G` is an N-by-N adjacency matrix that represents a graph. Nonzero entries in matrix `G` represent the weights of the edges.

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 (G, 'PropertyName', PropertyValue, ...)``` calls `graphallshortestpaths` with optional properties that use property name/property value pairs. You can specify one or more properties in any order. Each `PropertyName` must be enclosed in single quotes and is case insensitive. These property name/property value pairs are as follows:

``` [dist] = graphallshortestpaths(G, ...'Directed', DirectedValue, ...)``` indicates whether the graph is directed or undirected. Set `DirectedValue` to `false` for an undirected graph. This results in the upper triangle of the matrix being ignored. Default is `true`.

```[dist] = graphallshortestpaths(G, ...'Weights', WeightsValue, ...)``` lets you specify custom weights for the edges. `WeightsValue` is a column vector having 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, `graphallshortestpaths` gets weight information from the nonzero entries in matrix `G`.

## References

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

 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).

## Version History

Introduced in R2006b

expand all

Warns starting in R2022a

Behavior changed in R2021b