De ce contează?
La poștă, în loc să ții o coadă unde de fiecare dată cauți scrisoarea cu cea mai mică prioritate (operație scumpă), pui plicurile în sertare numerotate: sertarul 0, sertarul 1, sertarul 2... Apoi golești sertarele în ordine, de la 0 în sus. Niciodată nu „cauți" minimul — el e mereu în primul sertar nevid. Algoritmul lui Dial face exact asta cu nodurile unui graf: le pune în „găleți" numerotate după distanță.
Intuiția
Dijkstra procesează nodurile în ordinea crescătoare a distanței. Ca să afle mereu
nodul cu distanța minimă, folosește un heap (coadă de priorități) — fiecare
operație costă log n. Dar dacă ponderile muchiilor sunt mici, distanțele
posibile sunt puține și mărginite. Atunci nu mai ai nevoie de heap: pui nodul cu
distanța d direct în găleata cu indicele d și parcurgi gălețile în ordine. E
o sortare prin numărare aplicată cozii de priorități.
Două fapte fac gălețile posibile. Unu: distanțele pe care Dijkstra le
finalizează cresc monoton — niciodată nu fixezi o distanță mai mică după una
mai mare. Doi: cu ponderi întregi în 0..C, orice distanță finită e un întreg
de cel mult C*(n-1). Împreună: un cursor care pleacă de la găleata 0 și
merge doar înainte vizitează toate distanțele în ordine — gălețile înlocuiesc
complet heap-ul.