allpaths

Encontra todos os caminhos simples entre dois nós.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

paths = allpaths(G, s, t)

Descrição

Um caminho é simples quando não repete nenhum nó. Os pesos são ignorados: toda rota conta, não só a mais barata, e para isso existe shortestpath. Em um dígrafo só aparecem rotas que seguem as direções das arestas.

A contagem pode explodir em grafos densos, já que o número de caminhos simples cresce, no pior caso, mais rápido que exponencialmente.

Argumentos de entrada

G

Um graph ou digraph.

s, t

Nós inicial e final, como índices ou nomes.

Argumentos de saída

paths

Cell array de vetores linha. Cada vetor lista os nós de um caminho de s a t.

Exemplo

Rotas de 1 a 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

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

Veja também

shortestpath allcycles bfsearch dfsearch