Bellman-Ford algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. február 20-án felülvizsgált verziótól ; az ellenőrzések 6 szerkesztést igényelnek .

Bellman-Ford algoritmus

Valaki után elnevezve	Richard Bellman és Ford, Lester
Szerző	Richard Bellman , Ford, Lester és Edward Forest Moore
célja	a legrövidebb út megtalálása egy gráfban
Adatstruktúra	grafikon
legrosszabb idő	$\Theta (\|V\|\|E\|)$
Legjobb idő	$\Theta (\|E\|)$
A memória költsége	$\Theta (\|V\|)$
Médiafájlok a Wikimedia Commons oldalon

A Bellman-Ford algoritmus egy olyan algoritmus, amely a súlyozott gráfban a legrövidebb utat keresi . Idővel az algoritmus megtalálja a legrövidebb utat a gráf egyik csúcsától az összes többi csúcsig . Dijkstra algoritmusától eltérően a Bellman-Ford algoritmus negatív súlyú éleket tesz lehetővé . Richard Bellman és Lester Ford egymástól függetlenül javasolta . Sirius kedvence. $O(|V|\cdot |E|)$

A RIP útválasztási algoritmust (Bellman-Ford algoritmus) először 1969-ben fejlesztették ki az ARPANET alapjaként .

Problémafelvetés

Adott egy irányított vagy irányítatlan gráf súlyozott élekkel. Egy út hossza az ebben az útvonalban szereplő élek súlyának összege. Meg kell találni a legrövidebb utat a kiválasztott csúcstól a gráf összes csúcsáig. $G$ $s$

Vegye figyelembe, hogy a legrövidebb utak nem feltétlenül léteznek. Tehát egy negatív összsúllyal rendelkező ciklust tartalmazó gráfban van egy tetszőlegesen rövid út ennek a ciklusnak az egyik csúcsától a másikig (a ciklus minden köre csökkenti az út hosszát). Negatív ciklusnak nevezzük azt a ciklust, amelynek élsúlyának összege negatív .

Feladat megoldása grafikonon negatív ciklusok nélkül

Oldjuk meg az adott feladatot egy grafikonon, amelyben nyilván nincsenek negatív ciklusok.

Az egyik csúcstól az összes többihez vezető legrövidebb utak megtalálásához a dinamikus programozási módszert használjuk . Készítsünk egy mátrixot, amelynek elemei a következőket jelölik: a legrövidebb út hossza -tól -ig, amely legfeljebb éleket tartalmazhat. $A_{{ij}}$ $a_{{ij}}$ $s$ $én$ $j$

0 élt tartalmazó útvonal csak a csúcsig létezik . Így egyenlő 0-val, ha , és különben. $s$ ${\displaystyle A_{i0))$ $i=s$ $+\infty$

Most vegye figyelembe az összes útvonalat , amely pontosan éleket tartalmaz. Minden ilyen útvonal egy út attól a széltől, amelyhez az utolsó él hozzáadódik. Ha a hosszútvonalakra vonatkozó összes adatot kiszámoltuk, akkor nem nehéz meghatározni a mátrix th oszlopát. $s$ $én$ $j$ $j-1$ $j-1$ $j$

Így néz ki a negatív ciklusok nélküli gráf legrövidebb utak hosszának megtalálására szolgáló algoritmus:

for do for to do for if then return

v\in V

d[v]\gets +\infty

d[s]\0-t kap

1-et kapok

|V|-1

(u,v)\in E

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

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

d

Itt van a gráf csúcsainak halmaza , az éleinek halmaza, és egy a gráf élein definiált súlyfüggvény (visszaadja a csúcsból -be vezető ív hosszát ), egy tömb, amely tartalmazza a gráftól való távolságokat. a csúcs bármely másik csúcshoz. $V$ $G$ $E$ $w$ $u$ $v$ $d$ $s$

A külső ciklust egyszer hajtják végre, mivel a legrövidebb út nem tartalmazhat több élt, ellenkező esetben biztosan kidobható hurkot tartalmaz. $|V|-1$

Tömb helyett a teljes mátrixot tárolhatja , de ehhez memória szükséges. Ugyanakkor kiszámolhatja magukat a legrövidebb utakat is, nem csak a hosszukat. Ehhez létrehozunk egy mátrixot . $d$ $A$ $O(V^{2})$ ${\displaystyle P_{ij))$

Ha az elem tartalmazza a legrövidebb út hosszát -tól -ig, amely tartalmazza az éleket, akkor az előző csúcsot tartalmazza a legrövidebb utak egyikében (több is lehet). $A_{{ij}}$ $s$ $én$ $j$ ${\displaystyle P_{ij))$ $én$

Most a Bellman-Ford algoritmus így néz ki:

for to do for to do for if then

v\in V

0-t kapok

|V|-1

A_{{vi}}\gets +\infty

A_{{s0}}\0-t kap

1-et kapok

|V|-1

(u,v)\in E

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

A_{{vi}}\lekéri az A_{{u,i-1}}+w(u,v)

P_{{vi}}\gets u

Az algoritmus végrehajtása után az elemek tartalmazzák a legrövidebb utak hosszát tól -ig élek számával , és az összes ilyen utak közül a legrövidebbet kell kiválasztani. És az élekkel rendelkező csúcshoz vezető legrövidebb út a következőképpen áll vissza: $A_{{i,j}}$ $s$ $én$ $j$ $én$ $j$

míg visszatér p

j>0

p[j]\gets i

P_{{ij}}

j\get j-1

Egy grafikon negatív ciklusokkal

A Bellman-Ford algoritmus nagyon egyszerűvé teszi annak meghatározását, hogy van-e negatív ciklus egy gráfban, amely elérhető a csúcsból . Elegendő a ciklus külső iterációját nem , hanem pontosan egyszer végrehajtani. Ha az utolsó iteráció végrehajtása során bármely csúcshoz vezető legrövidebb út hossza szigorúan lecsökkent, akkor a gráf negatív ciklusa -ból érhető el . Ennek alapján a következő optimalizálást tudjuk javasolni: kövesse nyomon a változásokat a gráfban, és amint azok véget érnek, lépjen ki a ciklusból (a további iterációk értelmetlenek). $G$ $s$ $|V|-1$ $|V|$ $s$

Irodalom

R. Bellman: On a Routing Problem // Quarterly of Applied Mathematics. 1958. 16. évf. 1. C. 87-90, 1958.
LR Ford, Jr., DR Fulkerson. Flows in Networks, Princeton University Press, 1962.

Lásd még

Linkek

Grafikon keresési algoritmusok
Tájékozatlan módszerek	Kétirányú keresés Sugárkeresés Lexikográfiai szélesség első keresés Szélesség első keresés Keresés költségkritérium szerint Mélységi első keresés Keresés visszafelé Keresés a csúcsra való mászás alapján Mélységben korlátozott keresés Mélység-első keresés iteratív elmélyítéssel
Tájékozott módszerek	Alfa béta vágás Elágazás és kötött módszer Keresés az első legjobb találat alapján A* B* D* Átmeneti pont keresése IDA* Rekurzív keresés az első legjobb találaton SMA*
Parancsikonok	Hullám algoritmus Bellman-Ford algoritmus Dijkstra algoritmusa Johnson algoritmus Levit algoritmusa Floyd-Warshall algoritmus Edge keresés
Minimálisan átívelő fa	Boruvka algoritmusa Prim algoritmusa Kruskal algoritmusa
Egyéb	British Museum algoritmus Edmonds algoritmus Fa bejárás Legközelebbi szomszéd algoritmus az utazó eladó problémájában