Motivazione

Dijkstra fa crescere un insieme di vertici di cui è già nota la distanza minima. Finalizza sempre il vertice non ancora finalizzato più vicino, quindi lo usa per migliorare (rilassare) le distanze dai suoi vicini.

Perché imparare Dijkstra?

• Ovunque: percorsi GPS, instradamento dei pacchetti di rete e qualsiasi ricerca del percorso a costo minimo.
• Un approccio greedy che funziona: un esempio chiaro di scelta greedy che garantisce matematicamente il risultato ottimale, purché i pesi siano non negativi.
• Fondamenta: la sua idea di rilassamento ricompare in A* e in altri algoritmi per i percorsi minimi.

Importante: Dijkstra presuppone che non ci siano pesi negativi. Per gli archi negativi serve Bellman-Ford, nel corso successivo.