Algoritmo de Dijkstra

Curso de Ciência da Computação

ALGORITMO DE DIJKSTRA

Manaus
2014

Elder Amaral de Carvalho B45183-1
Geraldo Pereira da Mota Filho B41EHG-4

ALGORITMO DE DIJKSTRA

Trabalho apresentado como exigência para avaliação do primeiro bimestre, em disciplina de Teoria dos Grafos do 5º Semestre do curso de Ciência da Computação da Universidade Paulista, sob orientação do Professor Lucio.

Manaus
2014
SUMÁRIO

1. INTRODUÇÃO

A questão da determinação de um caminho mais curto entre duas cidades num mapa das estradas é um problema de caminho mínimo. Ou seja, se a cada arco/ramo associarmos o tempo ou o custo gasto a percorrê-lo, teríamos situações que se encaixam neste tipo de algoritmo, se pretendêssemos o tempo ou o custo mínimo entre dois determinados nós. Na primeira situação, se considerarmos todas as hipóteses que existem para ir, por exemplo, de Paços de Ferreira para Santo Tirso, a tarefa de determinar a distância mais curta afigura-se complicada. Neste trabalho, tentar-se-á mostrar uma forma eficiente de resolver tal problema através da explanação do algoritmo de Dijkstra.

2. DEFINIÇÃO

O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger Dijkstra em 1956 e publicado em 19591 2 , soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo, em tempo computacional O([m+n]log n) onde m é o número de arestas e n é o número de vértices. O algoritmo que serve para resolver o mesmo problema em um grafo com pesos negativos é o algoritmo de Bellman-Ford, que possui maior tempo de execução que o Dijkstra.
O algoritmo de Dijkstra assemelha-se ao BFS, mas é um algoritmo guloso, ou seja, toma a decisão que parece ótima no momento. Para a teoria dos grafos uma "estratégia gulosa" é conveniente já