Ve fyzice je potenciál fyzikální veličina, která popisuje potencionální energii v poli. Například elektrický potenciál popisuje energii v elektrickém poli. Potenciálový rozdíl mezi místy A, B je množství práce, které musíme vykonat, abychom přenesli jednotkový náboj z místa A do místa B.1 Nezáleží na cestě, kudy náboj přenášíme, ale jen na výchozím a cílovém bodě.

Potenciál a vzdálenost v grafu od počátečního vrcholu $s$ mají hodně společného. Když jdeme po hraně směrem od $s$, tak vzdálenost roste. Když půjdeme na opačnou stranu, tak klesá. Když vyjdeme z vrcholu $v$ na procházku, tak se vzdálenost bude měnit, ale po návratu do $v$ bude stejná jako na začátku.

Označme délku nejkratší cesty z $s$ do $v$ pomocí $y_v$. Pro každou hranu $vw$ je $y_v+c(vw)\geq y_w$, jinak můžeme cestu z $s$ do $w$ zkrátit (hrana $vw$ musí být korektní). Tím se necháme inspirovat.

Definice: Je dán orientovaný graf $G=(V,E)$ s ohodnocením hran $c(e)$ a s počátečním vrcholem $s$. Vektor $y=(y_v\,:\,v\in V)$ je přípustný potenciál pro graf $G$, ohodnocení $c$ a počátek $s$, pokud splňuje
$$\begin{eqnarray} (i) & y_v+c(vw)\geq y_w & \mbox{pro každou hranu $vw\in E$} \\ (ii) & y_s=0. & \end{eqnarray}$$

Hladinu nulového potenciálu si můžeme nastavit jak chceme, protože i po přičtením stejné konstanty ke každému $y_v$ zůstane první podmínka platná. Druhá podmínka říká, že si hladinu nulového potenciálu nastavíme tak, aby byl v počátečním vrcholu nulový.2

Pro lepší představu o potenciálu si představíme následující gumičkovou realizaci. Místo vrcholů vezmeme kuličky a pokud jsou vrcholy spojeny hranou délky $c(vw)$, tak je spojíme gumičkou, která se natáhne nejvýše do délky $c(vw)$. Při roztažení do větší délky praskne. Vrcholy přišpendlíme na vysoký sloup do takové výšky, kolik je $y_v$. Potenciál je přípustný, pokud žádná gumička nepraskne ($y_w – y_v \leq c(vw)$) a vrchol $s$ bude umístěn ve výšce $0$.

Pozorování: Přípustný potenciál je dolním odhadem na délku nejkratší cesty.

Pro každou hranu $vw$ platí $c(vw)\geq y_w – y_v$. Posčítáním těchto odhadů podél libovolné cesty $sPv=v_0 e_1 v_1\, \dots\, e_k v_k$, kde $s=v_0$ a $v=v_k$, dostaneme $$c(sPv) = \sum_{i=1}^{k} c(e_i) \geq \sum_{i=1}^{k} y_{v_i} – y_{v_{i-1}} = y_{v_k} – y_{v_0} = y_v. $$

Dokonce jsme ukázali víc. Ukázali jsme, že potenciálový rozdíl $y_{w} – y_{v}$ je dolním odhadem na délku libovolné cesty z $v$ do $w$.

Pozorování: Graf má přípustný potenciál právě tehdy, když neobsahuje záporný cyklus.

První implikace je jednoduchá. Předpokládejme, že graf má přípustný potenciál $y$ a obsahuje záporný cyklus $C$. Podle předchozího pozorování je potenciálový rozdíl dolním odhadem na délku cesty. Z toho dostaneme odhad na délku cyklu $c(C)=\sum_{e\in C} c(e) \geq 0$. To je spor s tím, že má cyklus zápornou délku.

K důkazu druhé implikace můžeme použít Bellman-Fordův algoritmus. Ten nám najde hodnoty $y_v$ (tj. délky nejkratších cest do všech vrcholů) právě tehdy, když graf neobsahuje záporný cyklus.

Úprava ohodnocení grafu pomocí potenciálu

Máme graf $G$, u kterého známe přípustný potenciál. Vytvoříme si nové ohodnocení grafu $c‘:E\to \RR$, které definujeme jako $c'(vw) = c(vw) + y_v – y_w$. Nové ohodnocení $c’$ nezmění nejkratší cesty, protože pro každou cestu $uPv$ platí $c'(uPv)=c(uPv)+y_u-y_v$ a potenciálový rozdíl mezi $u$ a $v$ je pro všechny cesty stejný. Pouze se změní ceny nejkratších cest.

Proto můžeme nejkratší cestu hledat i v grafu $G$ s ohodnocením $c’$ a nalezená nejkratší cesta bude stejná jako v grafu s původním ohodnocením.

Důležitá poznámka: Pro tuto úvahu jsme používali pouze vlastnost $(i)$ z definice přípustného potenciálu. Hladina nulového potenciálu mohla být nastavena libovolně.

Když známe přípustný potenciál, tak se můžeme zbavit záporných hran tím, že ke hranám přičteme vhodný násobek potenciálových rozdílů konců hran. Na graf s novým ohodnocením, tj. bez záporných hran, už můžeme použít Dijkstrův algoritmus. Využití viz Johnsonův algoritmus.

Příklad: V následujícím grafu chceme spočítat nejkratší cestu z $A$ do všech ostatních vrcholů. V grafu se zápornými hranami (levý obrázek) spočítáme přípustný potenciál pomocí Bellman-Fordova algoritmu (vzdálenost vrcholu od $A$ je přípustným potenciálem). Jako výstup dostaneme strom nejkratší cesty a přípustný potenciál (prostřední obrázek). Výše popsaným způsobem upravíme ohodnocení hran a dostaneme graf na pravém obrázku. Graf s novým ohodnocením má stejný strom nejkratší cesty jako graf s původním ohodnocením.



Původní graf se záporným ohodnocením.

Strom nejkratší cesty a přípustný potenciál.

Graf s upraveným ohodnocením bez záporných hran.

Jak najít přípustný potenciál? Můžeme si ho spočítat Bellman-Fordovým algoritmem. To už ale samo obnáší nalezení nejkratší cesty. Zkusme to ještě jinak.

Pokud náš graf odpovídá silniční síti, tak můžeme za přípustný potenciál ve vrcholech zvolit jejich vzdálenost od startu vzdušnou čarou.

A teď otázka pro vás. Můžeme za přípustný potenciál zvolit vzdálenost vzdušnou čarou od libovolného pevného vrcholu? Ano, můžeme. Bod $(i)$ z definice přípustného potenciálu je splněn. Abychom splnili bod $(ii)$, tak musíme nastavit hladinu nulového potenciálu tak, aby byla ve vrcholu $s$ nulová. Toho docílíme přičtením vhodné konstanty (jaké?). Jak jsme si ale ukázali při úpravě ohodnocení grafu pomocí potenciálu, pro nalezení nejkratších cest není hladina nulového potenciálu podstatná. Můžeme si jí zvolit libovolně, jen už pak nemůžeme mluvit o přípustném potenciálu.

V následujích odstavcích si vysvětlíme, proč je nejlepší zvolit za potenciál vzdálenost od cíle $t$.

Heuristika pro Dijkstrův algoritmus

Dijkstrův algoritmus hledá nejkratší cestu rovnoměrně na všechny strany — prochází všechny vrcholy v pořadí určeném vzdáleností od počátku. Tedy i když hledáme cestu z Prahy do Brna, tak ve “vlně” kolem 120 kilometrů spočítáme nejkratší cestu do Jihlavy i do Karlových Varů. Přitom nám bude pouhým pohledem do mapy jasné, že je výpočet nejkratší cesty do Karlových Varů zbytečný, protože od Prahy leží na opačné straně než Brno. I kdybychom z Karlových pokračovali do Brna vzdušnou čarou, tak to bude mnohem více kilometrů než po nejkratší cestě z Prahy do Brna. Proto chceme Dijkstrovu algoritmu pomoci tak, aby nejdříve hledal nejkratší cestu do vrcholů správným směrem.

Co kdybychom v Dijkstrově algoritmu počítali místo $\ARRAY{d}{v}$ se vzdáleností $\ARRAY{d‘}{v} :=\ARRAY{d}{v}+$vzdálenost z $v$ do cíle vzdušnou čarou. Pak bychom nejkratší cestu do Jihlavy spočítali dříve než do Karlových Varů. Vrcholy poblíž cíle by byly zvýhodněny. Ale bude to fungovat? Ano, k $\ARRAY{d}{v}$ jsme přičetli něco podobného přípustnému potenciálu, až na nastavení hladiny nulového potenciálu, ale to není pro hledání nejkratších cest potřeba.

Nyní celý algoritmus zopakujeme. Nechť $G$ je graf, který odpovídá silniční síti. Vzdálenost vrcholů od cíle vzdušnou čarou je téměř přípustným potenciálem (až na nastavení hladiny nulového potenciálu). Nejkratší cestu budeme hledat v grafu $G$ s ohodnocením $c’$, které je upraveno podle potenciálu. To nám zajistí, že vlny, ve kterých Dijkstra prohledává vrcholy, budou trochu zdeformovány a protaženy správným směrem.