shortestpathtree

Árvore de caminhos mínimos a partir de um nó de origem.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

T = shortestpathtree(G, s)

Descrição

Os caminhos mínimos a partir de uma origem nunca precisam se separar e se juntar, de modo que juntos formam uma árvore com raiz em s. Seguir as arestas da árvore de s até qualquer nó reproduz shortestpath(G, s, nó).

Esta é a estrutura calculada pelo algoritmo de Dijkstra.

Argumentos de entrada

G

Um graph ou digraph com pesos não negativos.

s

Nó de origem, como índice ou nome.

Argumentos de saída

T

Um grafo com os nós de G e, para cada nó alcançável diferente de s, a única aresta pela qual chega seu caminho mínimo. Os pesos das arestas são mantidos.

Exemplo

Árvore a partir do nó 1

D = digraph([1 1 2 3 4], [2 3 4 4 5], [1 4 2 1 3]);
T = shortestpathtree(D, 1);
disp(T.Edges)
numedges(T)

    EndNodes    Weight
    ________    ______

     1    2       1   
     1    3       4   
     2    4       2   
     4    5       3   
ans = 4

Observações

Restringir a árvore a destinos escolhidos (shortestpathtree(G, s, t)) e a opção 'OutputForm' são aceitos, mas ignorados: a árvore completa é retornada.

Veja também

shortestpath distances minspantree bfsearch