V článku o prehľadávaní do širky sme sa snažili hľadať najkratšiu cestu v grafe. Presnejšie, mali sme graf s $n$ vrcholmi a $m$ hranami a snažili sme sa nájsť najmenší počet hrán na ceste z vrchola $a$ do vrchola $b$. Všimnime si však, že všetky hrany boli rovnocenné. To ale často nezodpovedá tomu, čo potrebujeme simulovať. Predstavme si, že náš graf bude predstavovať cestnú sieť Slovenska. Každý vrchol bude zastupovať jedno okresné mesto. Je potom jasné, že hrana medzi Bratislavou a Pezinkom nie je rovnocenná hrane medzi Trebišovom a Michalovcami. Ak chceme, aby bola naša cestná sieť dostatočne presná, každej hrane by sme museli priradiť aj číslo, ktoré reprezentuje jej dĺžku.
Dostávame preto problém, v ktorom vystupujú ohodnotené hrany. Každá hrana má priradené nezáporné číslo, ktoré reprezentuje jej dĺžku. Našou úlohou je opäť nájsť najkratšiu cestu medzi vrcholmi $a$ a $b$, nezaujíma nás však počet hrán, cez ktoré prejdeme, ale súčet dĺžok týchto hrán.