Bellman-Fordův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 20. února 2019; kontroly vyžadují 6 úprav .

Bellman-Fordův algoritmus

Pojmenoval podle	Richard Bellman a Ford, Lester
Autor	Richard Bellman , Ford, Lester a Edward Forest Mooreovi
účel	nalezení nejkratší cesty v grafu
Datová struktura	graf
nejhorší čas	$\Theta (\|V\|\|E\|)$
Nejlepší čas	$\Theta (\|E\|)$
Náklady na paměť	$\Theta (\|V\|)$
Mediální soubory na Wikimedia Commons

Algoritmus Bellman-Ford je algoritmus pro nalezení nejkratší cesty ve váženém grafu . Algoritmus časem najde nejkratší cesty z jednoho vrcholu grafu ke všem ostatním. Na rozdíl od Dijkstrova algoritmu umožňuje Bellman-Fordův algoritmus hrany se zápornými vahami . Nezávisle navrhl Richard Bellman a Lester Ford . Oblíbený Siriusem. $O(|V|\cdot |E|)$

Směrovací algoritmus RIP (algoritmus Bellman-Ford) byl poprvé vyvinut v roce 1969 jako základ pro ARPANET .

Problémové prohlášení

Je dán orientovaný nebo neorientovaný graf s váženými hranami. Délka cesty je součtem vah hran zahrnutých v této cestě. Je potřeba najít nejkratší cesty z vybraného vrcholu do všech vrcholů grafu. $G$ $s$

Všimněte si, že nejkratší cesty nemusí existovat. Takže v grafu obsahujícím cyklus se zápornou celkovou váhou existuje libovolně krátká cesta z jednoho vrcholu tohoto cyklu do druhého (každé kolo cyklu zkracuje délku cesty). Cyklus, jehož součet vah hrany je záporný, se nazývá záporný cyklus .

Řešení úlohy na grafu bez záporných cyklů

Vyřešme daný problém na grafu, ve kterém evidentně nejsou žádné negativní cykly.

K nalezení nejkratších cest z jednoho vrcholu ke všem ostatním používáme metodu dynamického programování . Sestrojme matici, jejíž prvky budou označovat následující: je délka nejkratší cesty od do obsahující pouze hrany. $A_{{ij}}$ $a_{{ij}}$ $s$ $i$ $j$

Cesta obsahující 0 hran existuje pouze po vrchol . Tedy rovná se 0 if , a jinak. $s$ ${\displaystyle A_{i0))$ $i=s$ $+\infty$

Nyní zvažte všechny cesty od do obsahující přesně hrany. Každá taková cesta je cestou od hrany, ke které se přidá poslední hrana. Pokud jsou již všechny údaje o délkových drahách vypočteny, pak není těžké určit tý sloupec matice. $s$ $i$ $j$ $j-1$ $j-1$ $j$

Takto vypadá algoritmus pro nalezení délek nejkratších cest v grafu bez záporných cyklů:

for do for to do for if then return

v\in V

d[v]\gets +\infty

d[s]\gets 0

dostávám 1

|V|-1

(u,v)\v E

d[v]>d[u]+w(u,v)

d[v]\gets d[u]+w(u,v)

d

Zde je množina vrcholů grafu , je množina jeho hran a je to váhová funkce definovaná na okrajích grafu (vrací délku oblouku vedoucího z vrcholu do ), je pole obsahující vzdálenosti od vrchol na jakýkoli jiný vrchol. $PROTI$ $G$ $E$ $w$ $u$ $proti$ $d$ $s$

Vnější smyčka se provede jednou, protože nejkratší cesta nemůže obsahovat více hran, jinak bude obsahovat smyčku, kterou lze rozhodně vyhodit. $|V|-1$

Místo pole můžete uložit celou matici , ale to vyžaduje paměť. Zároveň si ale můžete spočítat samotné nejkratší cesty, a nejen jejich délky. K tomu vytvoříme matici . $d$ $A$ $O(V^{2})$ ${\displaystyle P_{ij))$

Pokud prvek obsahuje délku nejkratší cesty od do obsahující hrany, pak obsahuje předchozí vrchol to v jedné z těchto nejkratších cest (může jich být několik). $A_{{ij}}$ $s$ $i$ $j$ ${\displaystyle P_{ij))$ $i$

Nyní Bellman-Fordův algoritmus vypadá takto:

pro pro dělat pro dělat pro jestliže pak _

v\in V

dostávám 0

|V|-1

A_{{vi}}\gets +\infty

A_{{s0}}\dostane 0

dostávám 1

|V|-1

(u,v)\v E

A_{{vi}}>A_{{u,i-1}}+w(u,v)

A_{{vi}}\gets A_{{u,i-1}}+w(u,v)

P_{{vi}}\dostane tě

Po provedení tohoto algoritmu prvky obsahují délky nejkratších cest od do s počtem hran a ze všech těchto cest by měla být vybrána ta nejkratší. A nejkratší cesta k vrcholu s hranami se obnoví následovně: $A_{{i,j}}$ $s$ $i$ $j$ $i$ $j$

při návratu p

j>0

p[j]\gets i

i\gets P_{{ij}}

j\gets j-1

Graf se zápornými cykly

Algoritmus Bellman-Ford umožňuje velmi snadno určit, zda existuje negativní cyklus v grafu, který je dosažitelný z vrcholu . Postačí provést vnější iteraci smyčky nikoli , ale právě jednou. Pokud se během provádění poslední iterace délka nejkratší cesty k libovolnému vrcholu striktně zkrátila, pak má graf negativní cyklus dosažitelný od . Na základě toho můžeme navrhnout následující optimalizaci: sledovat změny v grafu a jakmile skončí, opustit smyčku (další iterace nebudou mít smysl). $G$ $s$ $|V|-1$ $|V|$ $s$

Literatura

R. Bellman: On a Routing Problem // Čtvrtletník aplikované matematiky. 1958. Vol 16, no. 1. C. 87-90, 1958.
LR Ford, Jr., DR Fulkerson. Flows in Networks, Princeton University Press, 1962.

Viz také

Odkazy

Algoritmy pro vyhledávání grafů
Neinformované metody	Obousměrné vyhledávání Hledání paprskem Lexikografická šířka první hledání Šířka první hledání Vyhledávání podle nákladového kritéria Hloubka první hledání Zpětné vyhledávání Hledejte podle výstupu na vrchol Hloubkově omezené hledání Hloubkové vyhledávání s iterativním prohlubováním
Informované metody	Výstřižek alfa beta Metoda větvení a vazby Hledejte podle první nejlepší shody A* B* D* Hledání přechodového bodu IDA* Rekurzivní vyhledávání první nejlepší shody SMA*
Zkratky	Vlnový algoritmus Bellman-Fordův algoritmus Dijkstrův algoritmus Johnsonův algoritmus Levitův algoritmus Floyd-Warshall algoritmus Hledání okrajů
Minimální kostra	Borůvkův algoritmus Primův algoritmus Kruskalův algoritmus
jiný	Algoritmus Britského muzea Edmondsův algoritmus Přechod stromu Algoritmus nejbližšího souseda v problému obchodního cestujícího