Představme si, že graf $G$ odpovídá silniční síti celé Evropy a má skoro milión vrcholů. Pokud chceme najít nejkratší cestu z Londýna do Budapešti, tak můžeme použít například Dijkstrův algoritmus. Ale co když se budeme na ptát na nejkratší cestu hodně často? Nemůžeme si něco předpočítat nebo nemůžeme použít nějakou fintu, abychom odpověď nalezli rychleji než Dijkstrovým algoritmem?

Co když chceme realizovat plánovač tras? To je internetový server, kterému zadáte odkud a kam jedete a on vám na mapě najde nejkratší cestu. Dokonce vám i vypíše instrukce, kam máte na které křižovatce odbočit. Takový server dostane během jediné vteřiny stovky dotazů a musí na ně stihnout odpovědět.

Prakticky se ukazuje, že když chcete jen někam hodně daleko, tak na začátku pojedete po lokálních silnicích. Pak najedete na dálnici a pojedete po ní skoro až do cíle.1 Poblíž cíle sjedete z dálnice a do cíle dojedete po lokálních silnicích.

Nyní využijeme předchozího pozorování o dálnicích a vysvětlíme si hlavní myšlenku dálničních hierarchií. V České republice je mnoho silnic, ale jen málo hraničních přechodů. Pokud budeme přes Českou republiku jen projíždět, tak nemusíme znát všechny silnice, ale stačí znát nejkratší cesty mezi libovolnými hraničními přechody. Ty můžeme mít předpočítané.

Když budeme hledat nejkratší cestu z Londýna do Budapešti, tak ji nebudeme hledat v celé silniční síti Evropy (to je příliš velký graf), ale ve $3$ fázích a v mnohem menších grafech. V první fázi najdeme nejkratší cesty z Londýna na hraniční přechody Velké Británie. Ve druhé fázi najdeme nejkratší cesty z hraničních přechodů Velké Británie do hraničních přechodů Maďarska. To hledáme ve zjednodušeném grafu evropské silniční sítě, který jako vrcholy obsahuje pouze hraniční přechody. Ve třetí fázi najdeme nejkratší cesty z hraničních přechodů Maďarska do Budapešti. Z výsledků všech $3$ fází poskládáme acyklický orientovaný graf, který obsahuje pouze Londýn, Budapešť a hraniční přechody Velké Británie a Maďarska. Ten už má jen pár vrcholů a navíc je acyklický, proto v něm nejkratší cestu můžeme najít v lineárním čase. Grafy ve všech fázích obsahují mnohem méně vrcholů, než silniční síť celé Evropy. Díky tomu dosáhneme zrychlení.

Hierarchie může mít i více úrovní. Celou Evropu se můžeme rozdělit na oblasti podle států, státy na oblasti podle krajů… Oblasti vůbec nemusí odpovídat právnímu rozdělení. Jde jen o to, aby každá oblast měla málo vstupních míst, tak zvaných portů (obdoba hraničních přechodů). Čím měně jich bude mít, tím více se zjednoduší graf obsahující pouze porty a hrany mezi nimi.

Problém dálničních hierarchií spočívá v tom, jak nalézt ty správné dálnice. Jak najít ty správné oblasti s malým počtem vstupních míst. To už je malinko složitější a je velké množství různých heuristik, které to řeší.2

Pro ilustraci časových úspor uvedeme příklad. Na grafu evropské silniční sítě trvá Dijkstrův algoritmus řádově desítky minut. Stejný dotaz řešený pomocí dálničních hierarchií trvá méně jak milisekundu.