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 | |
Nejlepší čas | |
Náklady na paměť | |
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.
Směrovací algoritmus RIP (algoritmus Bellman-Ford) byl poprvé vyvinut v roce 1969 jako základ pro ARPANET .
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.
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 .
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.
Cesta obsahující 0 hran existuje pouze po vrchol . Tedy rovná se 0 if , a jinak.
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.
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 returnZde 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.
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.
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 .
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).
Nyní Bellman-Fordův algoritmus vypadá takto:
pro pro dělat pro dělat pro jestliže pak _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ě:
při návratu pAlgoritmus 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).
Algoritmy pro vyhledávání grafů | ||
---|---|---|
Neinformované metody | ||
Informované metody | ||
Zkratky | ||
Minimální kostra | ||
jiný |