ENTRADA: Grafo não-direcionado G = (V, E, W) com peso w definido para cada aresta.
SAÍDA: Árvore geradora de custo mínimo de G.
2. (Estude as páginas 367 a 412 do livro de Sara Baase.)
Implementar o algoritmo de Dijkstra para, dado um grafo
G = (V, E, W), encontrar o menor caminho entre v
e os demais vértices do grafo. Em seguida, para cada
vértice w em G, imprima a
seqüência de vértices
que constitui o caminho de v até w.
ENTRADA: Grafo não-direcionado G = (V, E, W) com peso w
definido para cada aresta.
SAÍDA: Uma lista com todos os vértices w
de G, com o
respectivo caminho mais curto entre v e w.
IMPORTANTE: A operação de minimalização deve ser implementada usando um
heap.
Retorna à página principal
do curso
[Última alteração em 23.maio.2001 por
katia.]