# graphshortestpath

(To be removed) Solve shortest path problem in graph

`graphshortestpath` will be removed in a future release. Use `shortestpath` or `shortestpathtree` instead.

## Syntax

``[dist,path,pred] = graphshortestpath(G,S) ``
``[___] = graphshortestpath(G,S,D)``
``[___] = graphshortestpath(___,Name,Value)``

## Description

````[dist,path,pred] = graphshortestpath(G,S) `determines the shortest paths from the source node `S` to all other nodes in the graph `G`. `dist` contains the distances from the source node to all other nodes. `path` contains the shortest paths to every node. `pred` contains the predecessor nodes of the shortest paths.```
````[___] = graphshortestpath(G,S,D)` determines the shortest path from the source node `S` to the target node `D` and returns any of the output arguments from the previous syntax.```
````[___] = graphshortestpath(___,Name,Value)` specifies additional options using one or more name-value pair arguments. Specify name-value pair arguments after any of the input argument combinations in the previous syntaxes.```

## Input Arguments

collapse all

Adjacency matrix, specified as an N-by-N matrix that represents a graph. Nonzero entries in the matrix represent the weights of the edges.

Data Types: `double` | `single` | `logical`

Source node, specified as a numeric node index.

Example: `2`

Data Types: `double`

Destination node, specified as a numeric node index.

Example: `5`

Data Types: `double`

### Name-Value Arguments

Specify optional pairs of arguments as `Name1=Value1,...,NameN=ValueN`, where `Name` is the argument name and `Value` is the corresponding value. Name-value arguments must appear after other arguments, but the order of the pairs does not matter.

Before R2021a, use commas to separate each name and value, and enclose `Name` in quotes.

Example: `[dist,path,pred] = graphshortestpath(G,1,5,'Method',Acyclic')` assumes `G` to be a directed acyclic graph when finding the shortest path from node `1` to node `5`.

Shortest path algorithm, specified as the comma-separated pair consisting of `'Method'` and one of these options.

OptionDescription

`'Dijkstra'` (default)

This algorithm assumes that all edge weights are positive values in `G`. The time complexity is `O(log(N)*E)`, where N and E are the number of nodes and the number of edges respectively.

`'BFS'`

This breadth-first search algorithm assumes that all weights are equal and that edges are nonzero entries in the adjacency matrix `G`. The time complexity is `O(N+E)`.

`'Bellman-Ford'`

This algorithm assumes that all edge weights are nonzero entries in `G`. The time complexity is `O(N*E)`.

`'Acyclic'`

This algorithm assumes that `G` is a directed acyclic graph and all edge weights are nonzero entries in `G`. The time complexity is `O(N+E)`.

Example: `'Method','Acyclic'`

Data Types: `char` | `string`

Directed or undirected graph flag, specified as a comma-separated pair consisting of `'Directed'` and `true` or `false`. If `false`, the function ignores the upper triangle of the adjacency matrix `G`.

Example: `'Directed',false`

Data Types: `logical`

Custom weights for edges in the matrix G, specified as a comma-separated pair consisting of `'Weights'` and a column vector. The vector must meet the following conditions.

• It must have one entry for every nonzero value (edge) in the matrix `G`.

• The order of the custom weights in the vector must match the order of the nonzero values in `G` when it is traversed columnwise.

You can specify zero-valued weights. By default, the function obtains the weight information from the nonzero entries in `G`.

Example: `'Weights',[1 2.3 1.3 0 4]`

Data Types: `double`

## Output Arguments

collapse all

Distances from the source node to all other nodes in the graph, returned as a numeric scalar or vector. `dist` is returned as a scalar if you specify a destination node as the third input argument.

The function returns `Inf` for nonreachable nodes and `0` for the source node.

Shortest paths from the source node to all other nodes, returned as a vector or cell array. It is returned as a vector if you specify a destination node. Each number represents a node index in the graph.

Predecessor nodes of the shortest paths, returned as a vector.

You can use `pred` to determine the shortest paths from the source node to all other nodes. Suppose that you have a directed graph with 6 nodes. The function finds that the shortest path from node 1 to node 6 is ```path = [1 5 4 6]``` and `pred = [0 6 5 5 1 4]`. Now you can determine the shortest paths from node 1 to any other node within the graph by indexing into `pred`. For example, to figure out the shortest path from node 1 to node 2, you can query `pred` with the destination node as the first query, then use the returned answer to get the next node. Repeat this procedure until the query answer is 0, which indicates the source node.

`pred(2) = 6; pred(6) = 4; pred(4) = 5; pred(5) = 1; pred(1) = 0;`
The results indicate that the shortest path from node 1 to node 2 is `1->5->4->6->2`.

 Dijkstra, E. W. "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik. Vol. 1, Number 1, 1959, pp. 269–271.

 Bellman, R. "On a Routing Problem." Quarterly of Applied Mathematics. Vol. 16, Number 1, pp. 87–90.

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