`allpaths`

Finds every simple path between two nodes.

Category: Mathematics > Graph and Network Algorithms

Syntax

paths = allpaths(G, s, t)

Returns the paths from node s to node t as a cell array.

Description

A path is simple when it does not repeat a node. Weights are ignored: every route counts, not only the cheapest, so use shortestpath for that. For a digraph only routes that follow the edge directions appear.

The count can explode on dense graphs, since the number of simple paths grows faster than exponentially in the worst case.

Input arguments

G: A graph or digraph.
s, t: Start and end nodes, as indices or names.

Output arguments

paths: Cell array of row vectors. Each vector lists the nodes of one path from s to t.

Example

Routes from 1 to 5

G = graph([1 1 2 2 3 4], [2 3 3 4 4 5]);
P = allpaths(G, 1, 5);
fprintf('%d paths\n', numel(P))
for k = 1:numel(P)
  disp(P{k})
end

Output

4 paths
     1     2     3     4     5
     1     2     4     5
     1     3     2     4     5
     1     3     4     5

allpaths