shortestpath

Caminho mínimo entre dois nós.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

p = shortestpath(G, s, t)

[p, d] = shortestpath(G, s, t)

Descrição

Sem pesos cada aresta tem comprimento 1 e o caminho tem o menor número de arestas. Com pesos minimiza-se o peso total, então um caminho mais longo em arestas pode vencer um mais curto. Em um dígrafo o caminho deve seguir as direções das arestas.

Quando vários caminhos empatam, um deles é devolvido. Para distâncias de um nó a todos os outros, distances ou shortestpathtree custa menos que chamar shortestpath repetidamente.

Argumentos de entrada

G

Um graph ou digraph. Os pesos das arestas, se existirem, são os comprimentos e não podem ser negativos.

s, t

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

Argumentos de saída

p

Vetor linha de nós de s a t, ou cell array de nomes para um grafo nomeado. Vazio se t não puder ser alcançado.

d

Comprimento total do caminho. Inf quando não há caminho.

Exemplo

Rota com pesos

D = digraph([1 1 2 3 4], [2 3 4 4 5], [1 4 2 1 3]);
[p, d] = shortestpath(D, 1, 5)
shortestpath(D, 5, 1)

p = 1×4

     1     2     4     5
d = 6
ans = 1×0 empty double row vector

Veja também

distances shortestpathtree allpaths bfsearch highlight