# allpaths

Find all paths between two graph nodes

## Description

`[___] = allpaths(`

specifies additional options using one or more name-value arguments. You can use any of the
output argument combinations in previous syntaxes. For example, you can specify
`G`

,`s`

,`t`

,`Name,Value`

)`MaxNumPaths`

and a scalar to limit the number of paths returned.

## Examples

### All Paths in Undirected Graph

Create an adjacency matrix for a complete graph with four nodes, and then create an undirected graph from the adjacency matrix. Plot the graph.

A = ones(4); G = graph(A); plot(G)

Calculate all paths in the graph that begin at node 1 and end at node 3.

paths = allpaths(G,1,3)

`paths=`*5×1 cell array*
{[ 1 2 3]}
{[1 2 4 3]}
{[ 1 3]}
{[1 4 2 3]}
{[ 1 4 3]}

### Edges Along Paths

The second output argument of `allpaths`

returns the edges that are along each path. This is particularly useful for multigraphs, where the edge index is required to uniquely identify the edges on the path.

Create a directed multigraph with eight nodes and 18 edges. Specify names for the nodes. Plot the graph with labeled nodes and edges.

s = [1 1 2 2 3 3 2 2 4 6 8 6 6 7 3 3 5 3]; t = [2 3 1 3 2 1 4 4 6 2 6 7 8 8 5 5 7 7]; names = {'A','B','C','D','E','F','G','H'}; G = digraph(s,t,[],names); p = plot(G,'EdgeLabel',1:numedges(G));

Calculate all paths between node A and node H. Specify two output arguments to also return the edge indices for edges along each path.

[paths,edgepaths] = allpaths(G,'A','H');

View the nodes and edges along the first path.

paths{1}

`ans = `*1x6 cell*
{'A'} {'B'} {'C'} {'E'} {'G'} {'H'}

edgepaths{1}

`ans = `*1×5*
1 4 9 13 17

Highlight the nodes and edges along the first path.

highlight(p,'Edges',edgepaths{1},'EdgeColor','r','LineWidth',1.5,'NodeColor','r','MarkerSize',6)

### Limit Number of Paths Returned

Use the `'MaxNumPaths'`

, `'MaxPathLength'`

, and `'MinPathLength'`

options to limit the number of paths returned by `allpaths`

.

Create an adjacency matrix for a complete graph with 20 nodes. Create an undirected graph from the adjacency matrix, omitting self-loops.

```
A = ones(20);
G = graph(A,'omitselfloops');
```

Since all of the nodes in the graph are connected to all other nodes, there are a large number of paths in the graph between any two nodes (more than `1.7e16`

). Therefore, it is not feasible to calculate all of the paths between two nodes since the results will not fit in memory. Instead, calculate the first 10 paths from node 2 to node 5.

`paths1 = allpaths(G,2,5,'MaxNumPaths',10)`

`paths1=`*10×1 cell array*
{[ 2 1 3 4 5]}
{[ 2 1 3 4 6 5]}
{[ 2 1 3 4 6 7 5]}
{[ 2 1 3 4 6 7 8 5]}
{[ 2 1 3 4 6 7 8 9 5]}
{[ 2 1 3 4 6 7 8 9 10 5]}
{[ 2 1 3 4 6 7 8 9 10 11 5]}
{[ 2 1 3 4 6 7 8 9 10 11 12 5]}
{[ 2 1 3 4 6 7 8 9 10 11 12 13 5]}
{[2 1 3 4 6 7 8 9 10 11 12 13 14 5]}

Now calculate the first 10 paths between node 2 and node 5 that have a path length less than or equal to 2.

paths2 = allpaths(G,2,5,'MaxNumPaths',10,'MaxPathLength',2)

`paths2=`*10×1 cell array*
{[ 2 1 5]}
{[ 2 3 5]}
{[ 2 4 5]}
{[ 2 5]}
{[ 2 6 5]}
{[ 2 7 5]}
{[ 2 8 5]}
{[ 2 9 5]}
{[2 10 5]}
{[2 11 5]}

Finally, calculate the first 10 paths between node 2 and node 5 that have a path length greater than or equal to 3.

paths3 = allpaths(G,2,5,'MaxNumPaths',10,'MinPathLength',3)

`paths3=`*10×1 cell array*
{[ 2 1 3 4 5]}
{[ 2 1 3 4 6 5]}
{[ 2 1 3 4 6 7 5]}
{[ 2 1 3 4 6 7 8 5]}
{[ 2 1 3 4 6 7 8 9 5]}
{[ 2 1 3 4 6 7 8 9 10 5]}
{[ 2 1 3 4 6 7 8 9 10 11 5]}
{[ 2 1 3 4 6 7 8 9 10 11 12 5]}
{[ 2 1 3 4 6 7 8 9 10 11 12 13 5]}
{[2 1 3 4 6 7 8 9 10 11 12 13 14 5]}

## Input Arguments

`s`

, `t`

— Source and target node IDs (as separate arguments)

node indices | node names

Source and target node IDs, specified as separate arguments of node indices or node names.

Value | Example |
---|---|

Scalar node index | `1` |

Character vector node name | `'A'` |

String scalar node name | `"A"` |

**Example: **`allpaths(G,2,5)`

computes all paths between node 2 and
node 5.

**Example: **`allpaths(G,'node1','node2')`

computes all paths between
the named nodes `node1`

and `node2`

.

### 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: **`allpaths(G,s,t,'MaxNumPaths',100)`

returns only the first 100
results in the lexicographic ordering of paths.

`MaxNumPaths`

— Maximum number of paths

nonnegative integer scalar

Maximum number of paths, specified as the comma-separated pair consisting of
`'MaxNumPaths'`

and a nonnegative integer scalar. This option is
useful when the number of paths between two nodes grows large enough to hit memory
limits. You can specify `MaxNumPaths`

to limit the number of paths
returned by `allpaths`

so that the results fit within available
memory.

**Example: **`allpaths(G,s,t,'MaxNumPaths',100)`

`MaxPathLength`

— Maximum path length

nonnegative integer scalar

Maximum path length, specified as the comma-separated pair consisting of
`'MaxPathLength'`

and a nonnegative integer scalar. This option
filters the results returned by `allpaths`

so that no paths with
length larger than the specified limit are returned. The length of a path is measured
by the number of edges in it, ignoring edge weights.

To find paths with a range of lengths, specify both
`'MaxPathLength'`

and `'MinPathLength'`

. To find
paths with an exact specified length, specify the same value for both
`'MaxPathLength'`

and `'MinPathLength'`

.

**Example: **`allpaths(G,s,t,'MaxPathLength',4)`

returns paths that
have a length less than or equal to 4.

**Example: **`allpaths(G,s,t,'MinPathLength',3,'MaxPathLength',5)`

returns paths that have a length of 3, 4, or 5.

`MinPathLength`

— Minimum path length

nonnegative integer scalar

Minimum path length, specified as the comma-separated pair consisting of
`'MinPathLength'`

and a nonnegative integer scalar. This option
filters the results returned by `allpaths`

so that no paths with
length smaller than the specified limit are returned. The length of a path is measured
by the number of edges in it, ignoring edge weights.

To find paths with a range of lengths, specify both
`'MaxPathLength'`

and `'MinPathLength'`

. To find
paths with an exact specified length, specify the same value for both
`'MaxPathLength'`

and `'MinPathLength'`

.

**Example: **`allpaths(G,s,t,'MinPathLength',2)`

returns paths that
have a length greater than or equal to 2.

**Example: **`allpaths(G,s,t,'MinPathLength',3,'MaxPathLength',5)`

returns paths that have a length of 3, 4, or 5.

## Output Arguments

`paths`

— Paths between specified nodes

cell array

Paths between specified nodes, returned as a cell array. Each element
`paths{k}`

contains the nodes that lie along one of the paths between
the specified source and target nodes. The paths are returned in lexicographical order.
If the source and target nodes `s`

and `t`

specify the
same node, then by convention `allpaths`

returns a single path
containing that node. If node `t`

is unreachable from node
`s`

, then `paths`

is empty.

The data type of the entries in `paths`

depends on the way
`s`

and `t`

are specified:

If

`s`

and`t`

are specified as numeric node indices, then each element`paths{k}`

is a numeric vector of node indices.If

`s`

and`t`

are specified as string node names, then each element`paths{k}`

is a string array of node names.If

`s`

and`t`

are specified as character vector node names, then each element`paths{k}`

is a cell array of character vector node names.

`edgepaths`

— Edges along each path

cell array

Edges along each path, returned as a cell array. Each element
`edgepaths{k}`

contains the edge indices for edges that lie along the
corresponding path, `paths{k}`

. If node `t`

is
unreachable from node `s`

, then `edgepaths`

is
empty.

## More About

### Graph Paths

A *path* in a graph is a set of graph edges that
can be followed from a defined starting node to reach a defined ending node. By convention,
the nodes along the path must be unique, so paths do not contain repeated nodes or
edges.

## Tips

The number of paths in a graph depends heavily on the structure of the graph. For some graph structures, the number of paths can grow exponentially with the number of nodes. For example, a complete graph with 12 nodes given by

`G = graph(ones(12))`

contains nearly 10 million paths between any two of its nodes. Use the`MaxNumPaths`

,`MaxPathLength`

, and`MinPathLength`

name-value pairs to control the output of`allpaths`

in these cases.

## Version History

**Introduced in R2021a**

## See Also

## Open Example

You have a modified version of this example. Do you want to open this example with your edits?

## MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

# Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

You can also select a web site from the following list:

## How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

### Americas

- América Latina (Español)
- Canada (English)
- United States (English)

### Europe

- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)

- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)