Compiladores

Desenvolvimento de
Aplicações Web

Prof. Anderson Fernandes Pereira Dos Santos

Rio de Janeiro
2014
2

3

O Algoritmo de Dijkstra
O Algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger Wybe Dijkstra em 1956 e publicado em 1959 é um dos algoritmos mais conhecidos que calcula o caminho de custo mínimo entre vértices de um grafo. Escolhido um vértice como raiz da busca, este algoritmo calcula seu custo mínimo para todos os demais vértices do grafo. Ele é bastante simples e com um bom nível de desempenho. Ele não garante, contudo, a exatidão da solução caso haja a presença de arcos com valores negativos. Este algoritmo parte de uma estimativa inicial para o custo mínimo e vai sucessivamente ajustando esta estimativa. Ele considera que um vértice estará fechado quando já tiver sido obtido um caminho de custo mínimo do vértice tomado como raiz da busca até ele. Caso contrário ele dito estar aberto.
A seguir, iremos detalhar a sua aplicação em um sistema simples para traçar rotas.

http://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra#CITEREFDijkstra1959 http://www.inf.ufsc.br/grafos/temas/custo-minimo/dijkstra.html 4

Descrição da Aplicação
Para esta atividade desenvolvemos uma aplicação web que simula uma consulta de rotas aéreas.
Na tela do sistema há uma tabela de preços fictícios pra algumas rotas fictícias pré-determinadas. Caso o usuário selecione uma cidade de origem e uma cidade de destino que já possua uma rota cadastrada na tabela de preços, o sistema retorna o valor já exibido na tabela. Caso o usuário selecione uma rota não cadastrada na tabela, o sistema irá calcular a melhor rota através do algoritmo de Dijkstra, tendo o valor da passagem como peso das arestas, e retornar ao usuário a rota detalhada e o seu valor final.

5

Classes Java
Nesta seção serão descritos os códigos de cada classe utilizada para a construção do sistema.

Classe “Dijsktra”
A classe “Dijkstra” é a classe que