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) ``
``[___] = graphshortestpath(G,S,D)``
``[___] = graphshortestpath(___,Name,Value)``

Description

example

````[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.```

example

````[___] = 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.```

Examples

collapse all

Create 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 ```

Display the graph.

```h = view(biograph(DG,[],'ShowWeights','on')) ```
```Biograph object with 6 nodes and 11 edges. ```

Find the shortest path 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 ```

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

`pred` contains predecessor nodes of the shortest paths from node 1, the source node, to all other nodes, not only the specified destination node. You can use `pred` to query the shortest paths from the source node to any other node in the graph.

For instance, to figure out the shortest path from node 1 to node 4 using the information in `pred`, query `pred` with the destination node as the first query. Then use the returned answer to get the next node. Repeat this procedure until you get the query answer as 0, which indicates the source node.

```next = pred(4) next = pred(next) next = pred(next) ```
```next = 5 next = 1 next = 0 ```

The results indicate that the shortest path from node 1 to node 4 is 1->5->4.

Create an undirected 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); % tril returns the lower triangular part of the matrix. 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 the graph.

```h = view(biograph(UG,[],'ShowArrows','off','ShowWeights','on')) ```
```Biograph object with 6 nodes and 11 edges. ```

Find the shortest path from node 1 to node 6. Set `'Directed'` to `false` to specify that the graph is not a directed graph.

```[dist,path,pred] = graphshortestpath(UG,1,6,'Directed',false) ```
```dist = 0.8200 path = 1 5 3 6 pred = 0 5 5 1 1 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) ```

Input Arguments

collapse all

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

Data Types: `double`

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 Pair Arguments

Specify optional comma-separated pairs of `Name,Value` arguments. `Name` is the argument name and `Value` is the corresponding value. `Name` must appear inside quotes. You can specify several name and value pair arguments in any order as `Name1,Value1,...,NameN,ValueN`.

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.

OptionDesciption

`'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 sparse 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 sparse 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`.

References

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

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

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

평가판 신청