De ce contează?
Conduci spre un oraș îndepărtat, dar GPS-ul tău nu vede toată harta deodată. Strategia lui e simplă și surprinzător de eficientă: dintre toate intersecțiile la care a calculat deja un timp de sosire, alege mereu pe cea mai apropiată încă neexplorată, „se mută” acolo și, din acel punct, recalculează drumurile spre vecini. Pentru că nu poate ajunge mai repede la cea mai apropiată intersecție pe niciun ocol, timpul ei e definitiv. Repetând, harta se descoperă de la centru spre margini. Asta e, în esență, algoritmul lui Dijkstra.
Intuiția
Ai un graf cu costuri pe muchii (kilometri, secunde, lei) și vrei drumul cel mai ieftin de la un nod sursă la toate celelalte. Ideea-cheie: ții pentru fiecare nod cea mai bună distanță găsită până acum, apoi extinzi mereu din nodul nevizitat cu distanța minimă. Acel nod nu mai poate fi îmbunătățit — distanța lui e finală — așa că, din el, încerci să scurtezi drumul spre vecini. Această „scurtare” se numește relaxare.
De ce e sigur să fixezi nodul nevizitat cu distanța minimă? Orice alt drum spre
el ar trebui să iasă din zona deja fixată printr-un alt nod nevizitat u — dar
dist[u] e cel puțin la fel de mare (altfel îl alegeam pe u), iar de acolo mai
aduni doar costuri >= 0. Niciun ocol nu poate coborî sub minim. Exact aici e
nevoie de costuri nenegative: o muchie negativă ar putea „plăti înapoi” ocolul
și ar dărâma garanția.