# shortestpath (biograph)

(Removed) Solve shortest path problem in biograph object

The function has been removed. Use the `shortestpath` function of `graph` or `digraph` instead.

## Syntax

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

## Arguments

 `BGObj` Biograph object created by `biograph` (object constructor). `S` Node in graph represented by an N-by-N adjacency matrix extracted from a biograph object, `BGObj`. `T` Node in graph represented by an N-by-N adjacency matrix extracted from a biograph object, `BGObj`. `DirectedValue` Property that indicates whether the graph represented by the N-by-N adjacency matrix extracted from a biograph object, `BGObj`, 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 or string that specifies the algorithm used to find the shortest path. Choices are:`'Bellman-Ford'` — Assumes weights of the edges to be nonzero entries in the N-by-N adjacency matrix. 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 the N-by-N adjacency matrix to represent edges. Time complexity is `O(N+E)`, where `N` and `E` are the number of nodes and edges respectively.`'Acyclic'` — Assumes the graph represented by the N-by-N adjacency matrix extracted from a biograph object, `BGObj`, to be a directed acyclic graph and that weights of the edges are nonzero entries in the N-by-N adjacency matrix. 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 the N-by-N adjacency matrix. 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 the N-by-N adjacency matrix extracted from a biograph object, `BGObj`. It must have one entry for every nonzero value (edge) in the N-by-N adjacency matrix. The order of the custom weights in the vector must match the order of the nonzero values in the N-by-N adjacency matrix when it is traversed column-wise. This property lets you use zero-valued weights. By default, `shortestpaths` gets weight information from the nonzero entries in the N-by-N adjacency matrix.

## Description

Tip

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

`[dist, path, pred] = shortestpath(BGObj, S)` determines the single-source shortest paths from node `S` to all other nodes in the graph represented by an N-by-N adjacency matrix extracted from a biograph object, `BGObj`. Weights of the edges are all nonzero entries in the N-by-N adjacency matrix. `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] = shortestpath(BGObj, S, T)` determines the single source-single destination shortest path from node `S` to node `T`.

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

``` [...] = shortestpath(..., 'Directed', DirectedValue, ...)``` indicates whether the graph represented by the N-by-N adjacency matrix extracted from a biograph object, `BGObj`, 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`.

`[...] = shortestpath(..., '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 the N-by-N adjacency matrix. 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 the N-by-N adjacency matrix to represent edges. Time complexity is `O(N+E)`, where `N` and `E` are the number of nodes and edges respectively.

• `'Acyclic'` — Assumes the graph represented by the N-by-N adjacency matrix extracted from a biograph object, `BGObj`, to be a directed acyclic graph and that weights of the edges are nonzero entries in the N-by-N adjacency matrix. 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 the N-by-N adjacency matrix. Time complexity is `O(log(N)*E)`, where `N` and `E` are the number of nodes and edges respectively.

`[...] = shortestpath(..., 'Weights', WeightsValue, ...)` lets you specify custom weights for the edges. `WeightsValue` is a column vector having one entry for every nonzero value (edge) in the N-by-N adjacency matrix extracted from a biograph object, `BGObj`. The order of the custom weights in the vector must match the order of the nonzero values in the N-by-N adjacency matrix when it is traversed column-wise. This property lets you use zero-valued weights. By default, `shortestpath` gets weight information from the nonzero entries in the N-by-N adjacency matrix.

## References

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

 Bellman, R. (1958). On a Routing Problem. Quarterly of Applied Mathematics 16(1), 87–90.

 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