Motivation
Lição 2 de 9 do curso Algoritmo de Dijkstra - Algoritmos de Grafos da Coddy.
Dijkstra expande um conjunto de vértices cuja distância mais curta já é conhecida. Ele sempre finaliza o vértice mais próximo que ainda não foi finalizado e, em seguida, o utiliza para melhorar (relaxar) as distâncias para seus vizinhos.
Por que aprender Dijkstra?
- Em todos os lugares: roteamento de GPS, roteamento de pacotes de rede e qualquer busca de caminho de custo mínimo.
- Algoritmo guloso que funciona: um exemplo claro de uma escolha gulosa que comprovadamente fornece o resultado ideal, desde que os pesos não sejam negativos.
- Fundação: sua ideia de relaxamento reaparece no A* e em outros algoritmos de caminho mais curto.
Importante: Dijkstra assume que não há pesos negativos. Arestas negativas precisam do Bellman-Ford, o próximo curso.
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.
