INF1010 - Grafos - Caminho mais curto

entrega: até sábado, dia 15/6, à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 na segunda-feira. O esqueleto para a implementação está em grafo.c e o arquivo de interface aqui. Estão disponíveis os mesmos 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 (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 de chars, visitados, que indique que nós já foram visitados, e um outro array contendo o valor do menor caminho encontrado até agora até cada nó do grafo, além do array a ser retornado.

Vamos fazer a implementação em dois passos:

1. (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.

   atenção: Entregue esta versão fazendo upload do arquivo com nome grafo1.c !!!

2. (5 pontos) Reimplemente a função 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.

   Sua implementação de heap pode ser bem baseada na que foi vista no laboratório 9, mas teremos que fazer algumas modificações. Em grafo.c deixei a declaração da estrutura de heap modificada:

   1. Cada item do heap agora é um struct contendo o id do nó e a prioridade (distância até a origem). A função listap_remove deve retornar o id do nó, apesar de retirar do struct toda informação sobre ele.
   2. Ao visitar um nó, o algoritmo pode encontrar novas, menores, distâncias entre a origem e os vizinhos deste nó. O heap terá que ser atualizado para isto. Uma nova operação, listap_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: Entregue esta versão fazendo upload do arquivo com nome grafo2.c !!!