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

To view all translated materials including this page, select Japan from the country navigator on the bottom of this page.

# shortestpath

Shortest path between two single nodes

## Syntax

``P = shortestpath(G,s,t)``
``P = shortestpath(G,s,t,'Method',algorithm)``
``````[P,d] = shortestpath(___)``````

## Description

example

````P = shortestpath(G,s,t)` computes the shortest path starting at source node `s` and ending at target node `t`. If the graph is weighted (that is, `G.Edges` contains a variable `Weight`), then those weights are used as the distances along the edges in the graph. Otherwise, all edge distances are taken to be `1`.```

example

````P = shortestpath(G,s,t,'Method',algorithm)` optionally specifies the algorithm to use in computing the shortest path. For example, if `G` is a weighted graph, then `shortestpath(G,s,t,'Method','unweighted')` ignores the edge weights in `G` and instead treats all edge weights as `1`.```

example

``````[P,d] = shortestpath(___)``` additionally returns the length of the shortest path, `d`, using any of the input arguments in previous syntaxes.```

## Examples

collapse all

Create and plot a directed graph.

```s = [1 1 2 3 3 4 4 6 6 7 8 7 5]; t = [2 3 4 4 5 5 6 1 8 1 3 2 8]; G = digraph(s,t); plot(G)```

Calculate the shortest path between nodes 7 and 8.

`P = shortestpath(G,7,8)`
```P = 7 1 3 5 8 ```

Create and plot a graph with weighted edges.

```s = [1 1 1 2 2 6 6 7 7 3 3 9 9 4 4 11 11 8]; t = [2 3 4 5 6 7 8 5 8 9 10 5 10 11 12 10 12 12]; weights = [10 10 10 10 10 1 1 1 1 1 1 1 1 1 1 1 1 1]; G = graph(s,t,weights); plot(G,'EdgeLabel',G.Edges.Weight)```

Find the shortest path between nodes 3 and 8, and specify two outputs to also return the length of the path.

`[P,d] = shortestpath(G,3,8)`
```P = 3 9 5 7 8 ```
```d = 4 ```

Since the edges in the center of the graph have large weights, the shortest path between nodes 3 and 8 goes around the boundary of the graph where the edge weights are smallest. This path has a total length of 4.

Create and plot a graph with weighted edges, using custom node coordinates.

```s = [1 1 1 1 1 2 2 7 7 9 3 3 1 4 10 8 4 5 6 8]; t = [2 3 4 5 7 6 7 5 9 6 6 10 10 10 11 11 8 8 11 9]; weights = [1 1 1 1 3 3 2 4 1 6 2 8 8 9 3 2 10 12 15 16]; G = graph(s,t,weights); x = [0 0.5 -0.5 -0.5 0.5 0 1.5 0 2 -1.5 -2]; y = [0 0.5 0.5 -0.5 -0.5 2 0 -2 0 0 0]; p = plot(G,'XData',x,'YData',y,'EdgeLabel',G.Edges.Weight);```

Find the shortest path between nodes 6 and 8 based on the graph edge weights. Highlight this path in green.

`[path1,d] = shortestpath(G,6,8)`
```path1 = 6 3 1 4 8 ```
```d = 14 ```
`highlight(p,path1,'EdgeColor','g')`

Specify `Method` as `unweighted` to ignore the edge weights, instead treating all edges as if they had a weight of 1. This method produces a different path between the nodes, one that previously had too large of a path length to be the shortest path. Highlight this path in red.

`[path2,d] = shortestpath(G,6,8,'Method','unweighted')`
```path2 = 6 9 8 ```
```d = 2 ```
`highlight(p,path2,'EdgeColor','r')`

## Input Arguments

collapse all

Input graph, specified as either a `graph` or `digraph` object. Use `graph` to create an undirected graph or `digraph` to create a directed graph.

Example: `G = graph(1,2)`

Example: `G = digraph([1 2],[2 3])`

Source node ID, specified as either a numeric node index or a node name.

Example: `shortestpath(G,2,5)` computes the shortest path between node 2 and node 5.

Example: `shortestpath(G,'node1','node2')` computes the shortest path between the named nodes `node1` and `node2`.

Target node ID, specified as either a numeric node index or a node name.

Example: `shortestpath(G,2,5)` computes the shortest path between node 2 and node 5.

Example: `shortestpath(G,'node1','node2')` computes the shortest path between the named nodes `node1` and `node2`.

### 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 single quotes (`' '`). You can specify several name and value pair arguments in any order as `Name1,Value1,...,NameN,ValueN`.

Example: ```P = shortestpath(G,s,t,'Method','acyclic')```

collapse all

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

OptionDescription
`'auto'` (default)

The `'auto'` option automatically selects the algorithm:

• `'unweighted'` is used for `graph` and `digraph` inputs with no edge weights.

• `'positive'` is used for all `graph` inputs that have edge weights, and requires the weights to be nonnegative. This option is also used for `digraph` inputs with nonnegative edge weights.

• `'mixed'` is used for `digraph` inputs whose edge weights contain some negative values. The graph cannot have negative cycles.

`'unweighted'`

Breadth-First computation that treats all edge weights as `1`.

`'positive'`

Dijkstra algorithm that requires all edge weights to be nonnegative.

`'mixed'` (only for `digraph`)

Bellman-Ford algorithm for directed graphs that requires the graph to have no negative cycles.

While `'mixed'` is slower than `'positive'` for the same problem, `'mixed'` is more versatile as it allows some edge weights to be negative.

`'acyclic'` (only for `digraph`)

Algorithm designed to improve performance for directed, acyclic graphs (DAGs) with weighted edges.

Use `isdag` to confirm if a directed graph is acyclic.

### Note

For most graphs, `'unweighted'` is the fastest algorithm, followed by `'acyclic'`, `'positive'`, and `'mixed'`.

Example: `shortestpath(G,s,t,'Method','acyclic')`

## Output Arguments

collapse all

Shortest path between nodes, returned as a vector of node indices if `s` and `t` are numeric, or as a cell array of node names if `s` and `t` are character vectors. `P` is empty, `{}`, if there is no path between the nodes.

If there are multiple shortest paths between `s` and `t`, then `P` contains only one of the paths. The path that is returned can change depending on which algorithm `Method` specifies.

Shortest path distance, returned as a numeric scalar. `d` is the summation of the edge weights between consecutive nodes in `P`. If there is no path between the nodes, then `d` is `Inf`.

## Tips

• The `shortestpath`, `shortestpathtree`, and `distances` functions do not support undirected graphs with negative edge weights, or more generally any graph containing a negative cycle, for these reasons:

• A negative cycle is a path that leads from a node back to itself, with the sum of the edge weights on the path being negative. If a negative cycle is on a path between two nodes, then no shortest path exists between the nodes, since a shorter path can always be found by traversing the negative cycle.

• A single negative edge weight in an undirected graph creates a negative cycle.