Pseudo Code
Lição 4 de 9 do curso Algoritmo de Dijkstra - Algoritmos de Grafos da Coddy.
dijkstra(n, edges, source):
dist = [INF, INF, ...]; dist[source] = 0
visited = all false
repeat n times:
u = unvisited vertex with smallest dist (none reachable -> stop)
visited[u] = true
for each edge (a -> b, weight w):
if a == u and dist[u] + w < dist[b]:
dist[b] = dist[u] + w
replace every remaining INF with -1
return dist- INF é apenas um número maior que qualquer distância real (por exemplo, 1000000000).
- Escolher o vértice não visitado com a menor distância a cada rodada é o coração ganancioso (greedy) de Dijkstra. Escanear a lista linear de arestas para relaxar mantém o código simples e funciona em qualquer linguagem.
Experimente você mesmo
Esta lição não inclui um desafio de código.
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Algoritmo de Dijkstra - Algoritmos de Grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity