Algoritmo de Dijkstra

Nesta lição, aprenderemos como encontrar caminhos mínimos em grafos ponderados usando o Algoritmo de Dijkstra. Vamos resolver o seguinte problema:

Dado um grafo conexo não direcionado com vértices e arestas com pesos não negativos e um vértice , encontraremos o menor caminho entre e todos os outros vértices

Considere que é o peso da aresta que liga a .

Para resolver este problema, utilizaremos o Algoritmo de Dijkstra. Este algoritmo consiste em várias etapas. Enquanto simulamos estes passos, vamos manter dois vetores:

• : o menor caminho encontrado até agora de para
• : , se e somente se, já encontramos o menor caminho de para

Inicialmente, só conhecemos a distância de a , que é . Assim, definiremos e todos os outros valores deste vetor para , o que indica que ainda não os alcançamos. Agora, vamos repetir os seguintes passos vezes:

1. Tome o vértice com a menor distância que ainda não tenha sido marcado
2. Defina como
3. Itere por todos os vizinhos de e defina para

Este é o Algoritmo de Dijkstra. Agora vamos compreender o nosso algoritmo passo a passo de uma forma mais profunda, provar algumas partes do mesmo e aprender as formas de o implementar.

Passo 1