UNIVERSIDADE SALVADORALUNO: CAIO DE ARAÚJO PEDREIRACURSO: SISTEMAS DE INFORMAÇÃODISCIPLINA: MATEMÁTICA APLICADA

Algoritmo de Dijkstra

O algoritmo de Dijkstra o qual o nome se origina de seu inventor, Edsger Dijkstra um cientista da computação, o algoritmo soluciona o problema do caminho mais curto num grafo orientado ou não orientado com suas arestas de peso não negativas, porém podendo aceitar valores nulos.

Segundo (GOLDBARG, 2005) a complexidade do algoritmo é quadrada, ou seja: O (n*n). O problema do caminho mais curto diz: dado um grafo G = (V, E) e um vértice s, obter o caminho mais curto de s para cada um dos outros vértices em G.

Com um grafo de arestas de pesos não negativos o algoritmo irá encontrar o menor caminho possível entre um vértice definido como origem e todos os outros vértices, para execução do algoritmo deve-se seguir os seguintes passos.

1. Cria-se um array de distancias (distancia) com um elemento para cada vértice do grafo e coloca-se 0 para o valor de inicio e infinito para todos os outros vértices;

2. Criar uma fila de prioridades (Q) com os mesmos valores do array de distancias, onde a cada iteração deve-se retornar e excluir da fila o vértice de menor distancia existente;

3. Criar um array (anterior) com um elemento para cada vértice do grafo, informando inicialmente todos os valores como nulo. Esta estrutura guardará o vizinho do vértice que faz parte do caminho mínimo.

4. Enquanto houver elementos em Q, extrair um elemento de Q;

Para cada vizinho do elemento extraído de Q fazer a verificação se o peso do próximo elemento é menor que o atual, se positivo a verificação deverá atualizar a distancia e armazenar o seu antecessor no array (anterior). Isso é feito até que a fila de prioridade (Q) seja vazia. Na figura abaixo, mostra-se o algoritmo em portugol.

ALGORITMO DE DIJKSTRA.

Sendo que:

• W(u,v) representa o peso que vai da aresta u a v.

• Representação onde u e v são vértices quaisquer e s o vértice inicial.

• recupera-min(Q) é uma fila de prioridades onde se extrai o elemento de maior prioridade na fila.

"A arte de programar consiste em organizar e dominar a complexidade" - Edsger W. Dijkstra