# Documentation

### This is machine translation

Translated by
Mouseover text to see original. Click the button below to return to the English version of the page.

# graphshortestpath

Solve shortest path problem in graph

## Syntax

```[dist, path, pred] = graphshortestpath(G, S) [dist, path, pred] = graphshortestpath(G, S, T) [...] = graphshortestpath(..., 'Directed', DirectedValue, ...) [...] = graphshortestpath(..., 'Method', MethodValue, ...) [...] = graphshortestpath(..., 'Weights', WeightsValue, ...) ```

## Arguments

 `G` N-by-N sparse matrix that represents a graph. Nonzero entries in matrix `G` represent the weights of the edges. `S` Node in `G`. `T` Node in `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`. `MethodValue` Character vector that specifies the algorithm used to find the shortest path. Choices are:`'Bellman-Ford'` — Assumes weights of the edges to be nonzero entries in sparse matrix `G`. Time complexity is `O(N*E)`, where `N` and `E` are the number of nodes and edges respectively.`'BFS'` — Breadth-first search. Assumes all weights to be equal, and nonzero entries in sparse matrix `G` to represent edges. Time complexity is `O(N+E)`, where `N` and `E` are the number of nodes and edges respectively.`'Acyclic'` — Assumes `G` to be a directed acyclic graph and that weights of the edges are nonzero entries in sparse matrix `G`. Time complexity is `O(N+E)`, where `N` and `E` are the number of nodes and edges respectively.`'Dijkstra'` — Default algorithm. Assumes weights of the edges to be positive values in sparse matrix `G`. Time complexity is `O(log(N)*E)`, where `N` and `E` are the number of nodes and edges respectively. `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, `graphshortestpaths` gets weight information from the nonzero entries in matrix `G`.

## Description

### Tip

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

`[dist, path, pred] = graphshortestpath(G, S)` determines the single-source shortest paths from node `S` to all other nodes in the graph represented by matrix `G`. Input `G` is an N-by-N sparse matrix that represents a graph. Nonzero entries in matrix `G` represent the weights of the edges. `dist` are the `N` distances from the source to every node (using `Inf`s for nonreachable nodes and `0` for the source node). `path` contains the winning paths to every node. `pred` contains the predecessor nodes of the winning paths.

`[dist, path, pred] = graphshortestpath(G, S, T)` determines the single source-single destination shortest path from node `S` to node `T`.

`[...] = graphshortestpath(..., 'PropertyName', PropertyValue, ...)` calls `graphshortestpath` 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:

``` [...] = graphshortestpath(..., '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 sparse matrix being ignored. Default is `true`.

`[...] = graphshortestpath(..., 'Method', MethodValue, ...)` lets you specify the algorithm used to find the shortest path. Choices are:

• `'Bellman-Ford'` — Assumes weights of the edges to be nonzero entries in sparse matrix `G`. Time complexity is `O(N*E)`, where `N` and `E` are the number of nodes and edges respectively.

• `'BFS'` — Breadth-first search. Assumes all weights to be equal, and nonzero entries in sparse matrix `G` to represent edges. Time complexity is `O(N+E)`, where `N` and `E` are the number of nodes and edges respectively.

• `'Acyclic'` — Assumes `G` to be a directed acyclic graph and that weights of the edges are nonzero entries in sparse matrix `G`. Time complexity is `O(N+E)`, where `N` and `E` are the number of nodes and edges respectively.

• `'Dijkstra'` — Default algorithm. Assumes weights of the edges to be positive values in sparse matrix `G`. Time complexity is `O(log(N)*E)`, where `N` and `E` are the number of nodes and edges respectively.

`[...] = graphshortestpath(..., '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, `graphshortestpath` gets weight information from the nonzero entries in matrix `G`.

## Examples

Example 52. Finding the Shortest Path in a Directed Graph
1. 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 h = view(biograph(DG,[],'ShowWeights','on')) Biograph object with 6 nodes and 11 edges.```

2. Find the shortest path in the graph from node 1 to node 6.

```[dist,path,pred] = graphshortestpath(DG,1,6) dist = 0.9500 path = 1 5 4 6 pred = 0 6 5 5 1 4```
3. Mark the nodes and edges of the shortest path by coloring them red and increasing the line width.

```set(h.Nodes(path),'Color',[1 0.4 0.4]) edges = getedgesbynodeid(h,get(h.Nodes(path),'ID')); set(edges,'LineColor',[1 0 0]) set(edges,'LineWidth',1.5)```

Example 53. Finding the Shortest Path in an Undirected Graph
1. 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 h = view(biograph(UG,[],'ShowArrows','off','ShowWeights','on')) Biograph object with 6 nodes and 11 edges.```

2. Find the shortest path in the graph from node 1 to node 6.

```[dist,path,pred] = graphshortestpath(UG,1,6,'directed',false) dist = 0.8200 path = 1 5 3 6 pred = 0 5 5 1 1 3```
3. Mark the nodes and edges of the shortest path by coloring them red and increasing the line width.

```set(h.Nodes(path),'Color',[1 0.4 0.4]) fowEdges = getedgesbynodeid(h,get(h.Nodes(path),'ID')); revEdges = getedgesbynodeid(h,get(h.Nodes(fliplr(path)),'ID')); edges = [fowEdges;revEdges]; set(edges,'LineColor',[1 0 0]) set(edges,'LineWidth',1.5)```

## References

[1] Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269-271.

[2] Bellman, R. (1958). On a Routing Problem. Quarterly of Applied Mathematics 16(1), 87-90.

[3] 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).