Enxontra menor caminho entre 2 pontos, djkstra

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ático foi 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 em modelar 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 auxilio do 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 custo