Trabalho 5 - Caminhos mais curtos ( Entrega: 16/11/2009)


Implemente uma heap, e utilize esta heap para implementar o algoritmo de Dijkstra
de caminhos mais curtos:

 Algoritmo:

   Leia G, e distancias d(v,w) para cada aresta (v,w) de G.
   Inicialize dist(v) = infinito e ant(v) = v para todo v em G.
   dist(1) = 0;  // vertice 1 e' a origem dos caminhos
   insira os vertices, com suas distancias, em uma heap;

   enquanto a heap nao estiver vazia
            
              retire v, o elemento de peso (distancia estimada) minimo da heap
              para cada vizinho w de v
                           se dist(v) + d(v,w) < dist(w)
                                   dist(w) = dist(v) + d(v,w)
                                   ant(w) = v
                                   atualize posicao de w na heap !

             
    para cada vertice w de G
       imprima w e d(w)
  

Entrada: a entrada consiste de uma linha, contendo 2 inteiros, n e m, correspondendo ao numero de vertices e arestas de um grafo direcionado. Seguem-se m linhas, uma por aresta, contendo triplas v w d, indicando que d(v,w) = d. Exemplo:

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

Saida: (vertice pai distancia)
1 1 0
2 1 3
3 1 1
4 1 2
 Voce deve guardar as arestas que saem de um vertice em uma lista de adjacencias do vertice, para poder implmentar o algoritmo de forma eficiente. Alem disto, deve saber em tempo O(1) em que posicao cada vertice do grafo se encontra na heap, de forma a poder atualizar sua prioridade de forma eficiente.