Algoritmo Dijkstra

O Algoritmo de Dijkstra é caracterizado como sendo um algoritmo guloso e de programação dinâmica, ele garante a convergência para caminhos ótimos e sempre encontra a melhor solução. O Dijkstra é bem similar ao Algoritmo de Prim, porém aplica a técnica de relaxamento nas arestas , em que é verificado se há possibilidades de melhorar um caminho mais curto até um determinado vértice, isto é realizado com a assistência de uma fila de prioridades, definindo qual o próximo vértice a ser visitado (menor peso). Logo, este processo faz com que ele sempre escolha o melhor caminho para se chegar à um vértice a partir de uma dada raiz.

Abaixo é apresentado o pseudocódigo do Algoritmo de Dijkstra:

FIGURA 1: Pseudocódigo Dijstra.

Uma possível implementação desse algoritmo é apresentada à seguir:

FIGURA 2: Implementação do Algoritmo de Dijstra.

Implementação:

Inicialmente é atribuído a todos os vértices do grafo peso infinito, e nenhum predecessor com exceção ao vértice raiz o qual recebe peso = 0. À partir desse vértice o código verifica todos os vizinhos deste e compara o peso de cada um com o peso do vértice mais o peso da aresta entre ele e seu vizinho. Caso o peso do caminho seja menor ocorre a substituição do peso e do predecessor.

Resultados:

Abaixo são apresentados os resultados obtidos para K=1, K=2, e K=3.

K = 1:

Figura 3: Grafo K=1.

K = 2:

Figura 4: Grafo K=2.

Percebe-se uma disputa entre os vértices 10 e 5 pela conquista do maior número de vértices.

K = 3:

Figura 5: Grafo K=3.

Percebe-se uma disputa entre os vértices 10, 5 e 3 pela conquista do maior número de vértices.