Vzdálenost mezi vrcholy $u$ a $v$ v ohodnoceném orientovaném grafu $d(u, v)$ je minimum z délek všech $uv$-cest případně $+\inf$ pokud žádná $uv$-cesta neexistuje.
V orientovaném grafu se $d(u, v)$ a $d(v, u)$ mohou lišit!
Délka $l(S)$ sledu $S$ je součet délek jeho hran
Pokud jsou délky hran kladné, pak pro každý $uv$-sled existuje $uv$-cesta stejné nebo menší délky
Pokud sled není také cestou, pak se v něm musí opakovat nějaké vrcholy.
Označme $t$ první vrchol který se na $uv$-sledu opakuje.
Část sledu mezi prvním a posledním výskytem vrcholu $t$ vystřihneme a získáme $uv$-sled stejné nebo menší délky, protože délky hran jsou kladné.
Opakováním tohoto postupu pro všechny pro všechny opakující se vrcholy dostaname $uv$-cestu
$\square$
Pokud jsou délky hran v $G = (V, E)$ kladné, pak pro libovolné dva vrcholy $u, v \in V$ existuje nejkratší $uv$-sled a ten je současně nejkratší $uv$-cestou.
Nejkratší cesta je jedním ze sledů.
Pokud by tvrzení neplatilo, musel by existovat nějaký kratší sled.
Ten by ovšem, podle předchozího lemmatu o zjednodušování sledů, šel zjednodušit na ještě kratší cestu.
$\square$
Jsou-li délky hran kladné, platí pro vzdálenosti trojúhelníková nerovnost: $d(u, v) \le d(u, w) + d(w, v)$ pro libovolné $u, v, w \in V$.
Pokud je $d(u, w)$ nebo $d(w, v)$ nekonečná, nerovnost triviálně platí.
V opačném případě uvažme spojení nejkratší $uw$-cesty s nejkratší $wv$-cestou.
To je nějaký $uv$-sled délky $d(u, w) + d(w, v)$ a ten, podle předchozího důsledku, nemůže být kratší než nejkratší $uv$-cesta, která má délku $d(u, v)$.
$\square$
Nechť jsou délky hran kladné, $P$ je nejkratší $uv$-cesta a $w$ leží na $P$.
Označme $P_{uw}$ část $P$ mezi $u$ a $w$ a $P_{wv}$ část $P$ mezi $w$ a $v$.
Pak $P_{uw}$ je nejkratší $uw$-cesta a $P_{wv}$ je nejkratší $wv$-cesta.
Podle definice a předchozího důsledku platí
Tedy všude musí být rovnost a $l(P_{uw}) = d(u, w)$ a $l(P_{wv}) = d(w, v)$.
$\square$
Problém nalezení délky nejkratší cesty mezi dvěma vrcholy pro graf ohodnocený obecnými (tedy i zápornými) délkami je NP-těžký – proto pro něj neočekáváme existenci efektivního algoritmu.
Pro některá speciální ohodnocení grafu efektivní algoritmy existují.
Dijkstrův algoritmus - předpokládá hrany nezáporné délky
Bellman-Fordův algoritmus - připouští záporné délky ale předpokládá neexistenci záporných cyklů