INF1010 - Grafos - Caminho mais curto

entrega: até sábado, dia 9/11, às 23h

Ainda usando a mesma representação de grafos vista na aula anterior, vamos implementar no lab de hoje o algoritmo de busca de caminhos mais curtos de Dijkstra, visto em sala. Estão disponíveis os arquivos de entrada grafo5.dat e grafo9.dat e um teste em testecaminho.c.

A função menorescaminhos retorna um novo array contendo, para cada nó j do grafo, qual o último nó visitado no caminho mais curto encontrado de no_inicial até j. Repare que este último nó é o nó anterior ao nó j no caminho do no_inicial ao nó j. (A informação sobre o último visitado é suficiente para descobrir todo o caminho da origem até o nó!). O array retornado deve conter uma posição a mais do que o número de nós do grafo, com essa posição contendo o valor -1 (para marcar o final do array).

Para implementar menorescaminhos, utilize um array auxiliar, visitados, que indique que nós já foram visitados, e um outro array auxiliar, caminhos, contendo o valor do menor caminho (distância) encontrado até agora para cada nó do grafo. O array caminhos também deve conter uma posição a mais (com o valor -1) para indicar o final do array. Inicialize as posições de caminhos com o valor INT_MAX para todos os nós diferentes do nó inicial (que terá o valor 0).

Vamos fazer duas implementações:

(5 pontos) Inicialmente, implemente a função menorescaminhos utilizando busca linear para descobrir o nó não visitado com menor distância à origem. A função menordist faz essa busca linear, caso deseje utilizá-la. O esqueleto para a implementação está em grafo.c e o arquivo de interface aqui.
(5 pontos) Vamos agora reimplementar menorescaminhos utilizando um heap de prioridades construído para armazenar nós não visitados e distâncias.
O custo de encontrar o nó não visitado com menor distância à origem é linear e faz o algoritmo ficar O(n²). Uma forma de diminuir este custo é usar um heap de prioridades para determinar o nó com menor distância a cada passo.
Note que ainda serão necessários os arrays visitados e caminhos para as visitas aos vizinhos do nó corrente!
Sua implementação de heap pode ser bem baseada na que foi vista no laboratório 9 (implementação para o lab 9 aqui), mas teremos que fazer algumas modificações. Em grafo_heap.c temos uma declaração da estrutura de heap e algumas funções já modificadas. Você pode consultar o código do laboratório 9 e adaptá-lo para implementar/completar as funções que estão faltando em grafo_heap.c. Note que os parâmetros podem estar um pouco diferentes da implementação usada no laboratório 9!
1. Cada item do heap agora é um struct contendo o id do nó e a prioridade (distância até a origem). A função heap_remove deve retornar o id do nó removido (o de menor prioridade/distância).
2. Após a determinação do nó inicial, você pode inserir no heap os demais nós. Como todos possuem distância igual (INT_MAX), não há necessidade de correções na inserção dos nós.
3. Ao visitar um nó, o algoritmo pode encontrar novas distâncias (menores) entre a origem e os vizinhos deste nó. O heap terá que ser atualizado para isto. Uma nova operação, heap_corrige, muda a prioridade (distância) de um determinado nó e corrige sua posição no heap.
  Para esta operação não ficar muito custosa, o heap agora contém um array chamado posnos, indexado pelo identificador do nó, que indica em que posição do heap o nó se encontra. (Se o nó não estiver mais no heap, coloque -1 nesta posição, por exemplo.) Todas as operações de inserção e correção do heap devem acertar posnos.

Atenção: Indique na área de texto da tarefa quais exercícios você implementou e testou, e copie e cole a saída dos testes finais. Entregue os arquivos grafo.c e grafo_heap.c.