Ve většině aplikací mají hrany jinou než jednotkovou délku, protože délka hrany odpovídá například délce úseku silnice.  Předpokládejme, že délky hran jsou nezáporná celá čísla. Jak najít nejkratší cestu teď?

Mohli byste navrhnout, abychom použili BFS úplně stejně jako v neohodnocených grafech. To by ale nefungovalo, protože přímá hrana z $s$ do $t$ může být mnohem delší než cesta vedoucí po dvou krátkých hranách.

Adaptace průchodu do šířky

Nemohli bychom BFS upravit tak, aby už fungovalo? Ano to se dá. Zamysleme se nad podstatou BFS.  Jednoduchá představa je, že vezmeme miliardu Číňanů, postavíme je do výchozího vrcholu $s$ a necháme je procházet graf. Všichni Číňané chodí stejně rychle a pokud z vrcholu vede více cest, po kterých se mohou vydat, tak se rozdělí.

Průchod hrany délky dva jim bude trvat stejně dlouho jako průchod dvou hran jednotkové délky. Proto můžeme virtuálně každou hranu délky $k$ rozdělit na $k$ jednotkových úseků tím, že na ni přidáme $k-1$ pomocných vrcholů.  Jinými slovy hranu délky $k$ nahradíme cestou délky $k$. Touto úpravou dostaneme graf $G’$.

Graf $G’$ už má jen hrany jednotkové délky a proto na nalezení nejkratší cesty můžeme použít BFS. Nejkratší cesta mezi původními  vrcholy v $G’$ odpovídá nejkratší cestě mezi stejnými vrcholy v $G$.

U grafů s vysokým ohodnocením hran je sledování průběhu algoritmu docela nudné, protože většinu času uvidíme jen to, jak Číňané postupují skrz hrany. Podívejme se například na graf $K_3$ s vrcholy $A$, $B$, $C$ a s ohodnoceními hran $c(AB)=100$, $c(AC)=120$ a $c(BC)=10$. Při zahájení průchodu z vrcholu $A$ budeme čekat $100$ časových jednotek, než Číňané dorazí do dalšího vrcholu. Jelikož dopředu známe délku hrany, po které se Číňané vydali, tak můžeme jít na chvíli spát a nastavit si budík na čas, kdy Číňané dorazí na druhý konec hrany.

Do každého vrcholu umístíme budík, který zazvoní v momentě, kdy do vrcholu dorazí Číňané. Budíky budou na začátku nastaveny na nekonečný čas. Pouze budík v počátečním vrcholu $s$ bude nastaven tak, aby zazvonil okamžitě. Pokud v průběhu algoritmu zjistíme, že do vrcholu dorazíme dříve, než kolik je aktuálně nastavený čas na budíku, tak budík přeřídíme na dřívější čas.

Během algoritmu stačí být vzhůru jen v momentech krátce po té, co zazvoní budík u některého vrcholu. Zbytek času můžeme klidně prospat. Vždy, když nás probudí budík, tak se podíváme do kterých vrcholů dorazili Číňané, na které vstoupili hrany a pokud některá hrana bude zkratkou vedoucí  do neprozkoumaného vrcholu, tak přeřídíme odpovídající budík na dřívější čas.  Pak už zase můžeme jít spát.

Protože přeřizování budíků probíhá pouze když jsme vzhůru, tak můžeme těsně před usnutím přesně určit, který budík zazvoní jako první.

Zpracování vrcholů v pořadí, jak v nich zvoní budíky, můžeme snadno realizovat použitím prioritní fronty. Na začátku všechny budíky vložíme do prioritní fronty, kde priorita každého budíku je čas zvonění. Postupně budeme budíky z fronty odebírat (v pořadí jak mají zvonit) a zpracovávat události ve vrcholech. Tím jsme právě odvodili Dijkstrův algoritmus.