Enxontra menor caminho entre 2 pontos, djkstra

Disponível somente no TrabalhosFeitos
  • Páginas : 8 (1987 palavras )
  • Download(s) : 0
  • Publicado : 24 de abril de 2013
Ler documento completo
Amostra do texto
UNIVERSIDADE FEDERAL DE ITAJUBÁ CAMPUS ITABIRA

ECO027 – Projeto e Analise de Algoritmos

PASSEIO POR ITABIRA

Alunos:

Henrique Matias Olivino Gusmão RA: 16622 Luiz Henrique de Almeida Campos RA: 16633 Luiz Otavio Nunes Moura da Rosa RA: 16635

Professor(a): Natalia Cosse Batista Data da Entrega: 25/11/2011

Itabira, 25 de Novembro de 2011

1- Introdução: Neste 2º trabalho práticofoi feita uma implementação do algoritmo de Dijkstra, para encontrar a menor distância entre dois pontos na cidade de Itabira. Foi feito um programa onde são inseridos os pontos que se deseja calcular as distancias. Por meio de uma estratégia gulosa o programa retorna o caminho mínimo entre os dois pontos.

2- Apresentação do problema e como foi solucionado a cada etapa: O problema consiste emmodelar o mapa de Itabira em um grafo, onde as arestas são as ruas e os vértices suas intersecções. Cada aresta possui seu respectivo peso (distância). O algoritmo de Dijkstra utiliza de uma estratégia gulosa para encontrar o menor caminho entre dois pontos. Com auxilio do mesmo podemos determinar a menor distância entre dois pontos quaisquer do mapa de Itabira. Para a solução do problema,primeiramente fizemos uma coleta de dados a partir do mapa apresentado, utilizando o Google Maps para medir as distâncias entre os pontos do mapa. Com isso modelamos um grafo ponderado e em seguida construímos sua matriz de adjacência para representação do mesmo. Após termos obtido todos os dados, implementamos o programa que faz a leitura da matriz de adjacência por meio de um arquivo .txt e com auxiliodo algoritmo de dijkstra que encontra o menor caminho. O menor caminho pode ser salvo em um arquivo .txt também. O algoritmo de Dijkstra funciona da seguinte forma: 1-É atribuído o valor "0" a estimativa do custo "s" (a raiz da busca) e infinito as demais estimativas. É atribuído um valor qualquer aos precedentes (o precedente de um vértice "t" é o vértice que precede "t" no caminho de customínimo de "s" para "t"). 2-Enquanto houver vértice aberto: (i)Seja "k" um vértice ainda aberto cuja estimativa seja a menor dentre todos os vértices abertos. (ii)Feche o vértice "k". (iii)Para todo vértice "j" ainda aberto que seja sucessor de "k" faça: Some a estimativa do vértice "k" com o custo do arco que une "k" a "j". Caso esta soma seja melhor que a estimativa anterior para o vértice "j",substitua-a e anote "k" como predecessor de "j".

Observação: Os dados foram obtidos a partir do mapa apresentado no site da disciplina. Como o zoom não foi o maior possível, algumas ruas foram simplificadas em apenas uma aresta. Porém o algoritmo é genérico e funciona tanto para 40 vértices como para 70. Devido ao grande número de provas e trabalhos tornou-se inviável refazer a coleta de dados.3- Explicação de como algoritmo funciona: O algoritmo faz a leitura do arquivo "vertices.txt"(onde esta localizado, o número de vértices, os vértices e a matriz de adjacência). A seguir é feita uma alocação dos vértices e das distâncias. Com isso podemos pegar o número de vértices e as distâncias dos mesmos. A matriz de adjacência é reescrita no arquivo "matriz.txt". Após a leitura dos dados, éperguntado ao usuário o nó de origem e o de destino, para que o algoritmo de Dijkstra possa encontrar o menor caminho entre esse dois pontos. A função “clock()” é chamada antes e após a função de Dijkstra para que se possa obter o tempo de execução de uma determinada solução. Com o termino do algoritmo são apresentados os resultados como o menor caminho em ordem decrescente e o tempo de execução. Èpossível salvar o caminho mínimo em um arquivo "caminho_minimo.txt".

4- Ordem de complexidade: A ordem de complexidade do algoritmo no pior caso é O(n²), onde n é o número de vértices.

5- Discussão se o algoritmo leva sempre a solução ótima: O algoritmo de Dijkstra permite determinar a solução ótima através da adição de vértices à árvore de caminho mínimo pelo processo de relaxamento de...
tracking img