Dlaczego trasa liczy się w milisekundach, a nie w dniach
Ta sama sieć dróg, ta sama trasa z A do B. Po lewej klasyczny algorytm Dijkstry „zalewa" mapę,
sprawdzając wszystko po kolei. Po prawej hierarchie kontrakcji: gotowe, prekalkulowane skróty przez główne drogi.
Naiwnie: algorytm Dijkstry (1959)
rozlewa się jak atrament – musi odwiedzić prawie wszystko między startem a celem
odwiedzone węzły:0
Sprytnie: hierarchie kontrakcji
dojazd do „autostrady", skok po prekalkulowanych skrótach, zjazd przy celu