A Bellman–Ford-algoritmus egy algoritmus, amely kiszámítja a legrövidebb utat egyetlen forrástól (csúcs) az összes többi csúcshoz egy súlyozott digráfban. Ez lassabb, mint Dijkstra algoritmusa ugyanarra a problémára, viszont sokoldalúbb, mert képes olyan gráfok kezelésére, amelyekben az egyes élsúlyok negatív számok. Az algoritmust először javasolta, azonban helyette Richard Bellman és Lester Ford Jr. után nevezték el, akik 1958-ban, illetve 1956-ban publikálták. Edward F. Moore is közzétette ugyanezt az algoritmust 1957-ben, ezért néha Bellman–Ford–Moore-algoritmusnak is nevezik.
A negatív élsúlyok a gráfok különböző alkalmazásaiban találhatóak, innen ered az algoritmus hasznossága. Ha egy gráf tartalmaz egy "negatív ciklust" (azaz egy olyan ciklust, amelynek élei összege negatív értékűek), amely elérhető a forrástól, akkor nincs legolcsóbb út: bármely olyan út, amelynek van egy pontja a negatív körön, olcsóbbá válhat egy további sétával a negatív ciklus mentén. Ilyen esetben a Bellman–Ford-algoritmus képes felismerni és jelenteni a negatív ciklust. bélyegkép|Ebben a példagráfban, feltételezve, hogy a forrás és az élek feldolgozása a legrosszabb sorrendben történik, jobbról balra, ez teljes | V | −1 vagy 4 iterációt igényel a távolságbecslések konvergenciájához. Ezzel szemben, ha az éleket a legjobb sorrendben, balról jobbra dolgozzuk fel, az algoritmus egyetlen iterációval konvergál Mint Dijkstra algoritmusa Bellman–Ford relaxáció útján megy végbe, amelyben a helyes távolságokhoz való közelítéseket jobbak váltják fel, amíg végül el nem érik a megoldást. Mindkét algoritmusban az egyes csúcsokhoz való hozzávetőleges távolság mindig a valós távolság túlbecslése, és helyébe a régi érték minimuma és az újonnan talált út hossza lép Dijkstra algoritmusa azonban prioritási sort használ, hogy mohón kiválassza a még nem feldolgozott legközelebbi csúcsot, és végrehajtja ezt a relaxációs folyamatot az összes kimenő élen; ezzel szemben a Bellman–Ford-algoritmus egyszerűen ellazítja az összes élt, és ezt meg is teszi alkalommal, ahol a csúcsok száma a gráfon. Ezen ismétlések mindegyikében növekszik a helyesen kiszámított távolsággal rendelkező csúcsok száma, amelyből az következik, hogy végül az összes csúcs megfelelő távolsággal fog rendelkezni. Ez a módszer lehetővé teszi a Bellman–Ford-algoritmus a Dijkstránál szélesebb bemeneti osztályra történő alkalmazását.
Bellman–Ford időben zajlik, ahol és a csúcsok és az élek száma.
function BellmanFord(list vertices, list edges, vertex source) is
// Az implementáció bemenete egy gráf, az alábbi módon ábrázolva: // vertices: csúcsok listája, [0..n-1] egész számokként, // és edges: élek listája, ahol az éleket számpárosok alkotják, pl. (u, v) // kitölt két tömböt (distance - távolság, predecessor - előd) melyek // a kiindulásból az egyes csúcsokhoz vezető legrövidebb utat tartalmazzák
distance := list of size n // távolság, n méretű lista predecessor := list of size n // előd, n méretű lista
// 1. lépés: a segédtömbök inicializálása for each vertex v in vertices do distance[v] := inf // kezdetben minden csúcs távolsága végtelen predecessor[v] := null // minden csúcs elődje null
// a kiindulás önmagától való távolsága nulla distance[source] := 0
// 2. lépés: az élek ismételt feloldása repeat |V|−1 times: // ismétlés |V|−1 -szer // minden (u, v) élhez egy w súly tartozik for each edge (u, v) with weight w in edges do if distance[u] + w < distance[v] then distance[v] := distance[u] + w predecessor[v] := u
// 3. lépés: negatív súlyú körutak ellenőrzése for each edge (u, v) with weight w in edges do if distance[u] + w < distance[v] then predecessor[v] := u // létezik negatív kör (ciklus); keressük meg a kör egy csúcspontját visited := list of size n initialized with false // hamis értékkel inicializált n hosszú lista visited[v] := true while not visited[u] do visited[u] := true u := predecessor[u] // u egy negatív kör csúcsa, keressük magát a kört ncycle := [u] // ncycle egy lista v := predecessor[u] while v != u do ncycle := concatenate([v], ncycle) v := predecessor[v] error "A gráf negatív súlyú kört tartalmaz", ncycle return distance, predecessor
Leegyszerűsítve, az algoritmus inicializálja a forráshoz való távolságot 0-ig, és minden többi csomópontot a végtelenig. Ezt követően az összes él esetében, ha a távolság a rendeltetési helyig lerövidíthető az él megvételével, a távolság az új, alacsonyabb értékre frissül. Minden egyes i iterációnál, az élek vizsgálatakor, az algoritmus megtalálja a leghosszabb i élek összes legrövidebb útját (és esetleg néhány i élnél hosszabb utat is). Mivel a kör nélküli lehető leghosszabb út lehet él, az éleket meg kell vizsgálni alkalommal annak biztosítékaként, hogy minden csomópontra megtalálták a legrövidebb utat. Az összes él végső vizsgálatát elvégzik, és amennyiben bármelyik távolságot frissítik, akkor megtalálják a hosszúságú élek útját, amely csak akkor fordulhat elő, ha legalább egy negatív kör létezik a gráfban.
A helyesség igazolása Az algoritmus helyessége indukcióval mutatható ki:
Állítás. Miután i ismétlést hajtunk végre a hurokra:
· ha az u távolság nem végtelen, akkor ez megegyezik az s- től u-ig tartó út hosszával; és · ha van egy út s-től u-ig, legfeljebb i éllel, akkor az (u) Távolság legfeljebb az s- től u-ig tartó legrövidebb út legfeljebb i éllel.
Bizonyítás. Az alapeset indukció, hogy i=0 és abban a pillanatban, mielőtt a először végrehajtódik. A forráscsúcs távolsága source.distance = 0, amely helyes. Más u csúcsok esetében u.distance = infinity, amely szintén helyes, mert nincs út a forrástól az u-hoz 0 éllel.
Az induktív esetre először az első részt bizonyítjuk. Vegyünk egy pillanatot, amikor egy csúcs távolsága frissül v.distance := u.distance + uv.weight által. Induktív feltételezés alapján u.distance a forrás és az u közötti útvonal hossza. Ezután u.distance + uv.weight a forrástól v-ig tartó út hossza, ezt követi a forrástól u- ig tartó út, majd v-ig megy.
A második részt illetően, gondoljunk a legrövidebb útra, mint P (lehet, hogy több van, mint egy) a forrástól a v-ig legfeljebb i éllel. Legyen u az utolsó csúcs a v előtt ezen az úton. Ezután az útnak a forrástól az u-ig tartó része a legrövidebb út legfeljebb i-1 éllel, mert ha nem így lenne, akkor lennie kellene valamilyen szigorúan rövidebb útnak a forrástól az u-ig legfeljebb i- 1 éllel, és ezt követően az uv élt hozzáfűzhetjük ehhez az úthoz annak érdekében, hogy elérjük az az utat legfeljebb i éllel, amely szigorúan rövidebb, mint P — ellentmondás. Induktív feltevéssel, az u.distance i -1 iterációt követően legfeljebb a forrástól u-ig tartó út hossza. Ezért uv.weight + u.distance legfeljebb a P hossza lehet. Az i edik iteráció, v.distance összehasonlításra kerül uv.weight + u.distance-el, és egyenlőre van állítva, ha uv.weight + u.distance kisebb. Ezért, i iterációt követően, v.distance legfeljebb a P hossza, azaz a forrástól v-ig tartó legrövidebb út, amely legfeljebb i élt használ.
Ha nincsenek negatív súlykörök, akkor minden legrövidebb út egyszerre ér minden egyes csúcshoz, tehát a 3. lépésben nem végezhetőek további javítások. Ezzel szemben tételezzük fel, hogy nem lehet fejlesztést elérni. Majd minden olyan körre, amelynek v , ..., v [ k −1] csúcsai vannak,
v[i].distance <= v[i-1 (mod k)].distance + v[i-1 (mod k)]v[i].weight
A ciklus mentén összegezve a v [ i ] .távolság és v [ i −1 (mod k )] távolság feltételei törlődnek, hátrahagyva:
0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight
Tehát minden körnek nem negatív súlya van.
Negatív körök keresése Amikor az algoritmust a legrövidebb út megtalálására használják, akkor a negatív körök léte problémát jelent, és ez akadályozza az algoritmust abban, hogy megtalálja a helyes megoldást.
Azonban, tekintettel arra, hogy az algoritmus negatív kör találatkor lezárul, a Bellman–Ford-algoritmus olyan alkalmazásokhoz alkalmazható, amelyekben ez a célkitűzés – például ciklus törlési technikáknál hálózat áramlás elemzésekor.
Alkalmazások az útválasztásban A Bellman–Ford-algoritmus megosztott változatát használják a távolságvektor útválasztási protokollokban, például az útválasztási információs protokollban (RIP). Az algoritmus azért került megosztásra, mert magába foglal számos csomópontot (útválasztót) egy autonóm rendszerben (AS), az IP-hálózatok egy gyűjteményén belül, amely jellemzően egy ISP tulajdonát képezi. A következő lépéseket tartalmazza:
Minden csomópont kiszámítja a távolságot a saját és az összes többi csomópont között az AS-en belül, és ezeket az információkat táblázatként tárolja. Minden csomópont elküldi a tábláját az összes szomszédos csomópontnak. Amikor egy csomópont távolságtáblákat kap szomszédaitól, kiszámítja a legrövidebb útvonalat az összes többi csomóponthoz, és frissíti saját tábláját, hogy bármilyen változást tükrözzön.
A Bellman–Ford-algoritmus fő hátrányai ebben a beállításban a következők:
Nem méretezhető jól. A hálózati topológiában bekövetkező változások nem tükröződnek gyorsan, mivel a frissítések csomópontonként terjednek. Végtelenségig kell számolni, ha a kapcsolat vagy a csomópont meghibásodása miatt a csomópont elérhetetlenné válik más csomópontok valamelyikéből, ezek a csomópontok örökké tarthatnak, fokozatosan növelve a hozzá rendelt távolság becsléseit, és időközben lehetnek útvonal hurkok.
Fejlesztések A Bellman–Ford-algoritmust a gyakorlatban fejleszthető (bár nem a legrosszabb esetben) azzal a megfigyeléssel, ha az algoritmus fő hurokjának iterációja változtatások nélkül befejeződik, az algoritmus azonnal megszüntethető, mert a későbbi iterációk nem fognak több változtatást végezni. Ezzel a korai lezárási feltétellel a fő ciklus néhány esetben |V|- 1-nél sokkal kevesebb iterációt használhat, annak ellenére, hogy az algoritmus legrosszabb esete változatlan marad.
Yen (1970) további két fejlesztést mutatott be a Bellman–Ford-algoritmushoz negatív súlyú kör nélküli gráfra vonatkozóan; újból, miközben az algoritmust a gyakorlatban gyorsabbá teszik, nem változtatják meg a legrosszabb eseti időkerethez kötöttséget. Első fejlesztése csökkenti azoknak a relaxációs lépéseknek a számát, amelyeket az algoritmus minden iterációjánál végre kell hajtani. Ha a v csúcs távolsági értéke nem változott, mivel az utóbbi időben v- n kívüli éleket lazítottuk meg, akkor nem szükséges a v-n kívüli éleket második alkalommal meglazítani. Ilyen módon, ahogy a helyes távolságértékekkel rendelkező csúcsok száma növekszik, minden egyes iterációnál csökken az a szám, amelynek kimeneti éleit lazítani szükséges, és ez állandó tényezős időmegtakarításhoz vezet sűrű gráf esetében.
A Yen második fejlesztése először néhány tetszőleges lineáris sorrendet rendel hozzá az összes csúcshoz, majd az összes él halmazát két részhalmazra bontja. Az első részhalmaz, E f, az összes élt ( v i, v j ) tartalmazza, i < j módon; a második, E b, éleket (v i, v j) tartalmazza i> j módon. Minden csúcsot v 1, v 2, ..., v |V| sorrendben meg lazítva minden kimenő élt az Ef ben lévő csúcstól. Ezután minden csúcsot meglátogatunk sorrendben V |, v | V | −1, ..., v 1, lazítva minden kimenő élt az E b-ben lévő csúcstól. Az algoritmus fő hurokjának minden egyes iterációja az első után legalább két élt ad hozzá az élekhez, amelyeknek lazított távolságai megegyeznek a legrövidebb helyes úttávolságokkal: egy az E f-től és egy E b-től. Ez a módosítás az algoritmus fő hurokjának legrosszabb eseti iteráció számát csökkenti |V|-1 től -re.Cormen et al., 2nd ed., Problem 24-1, pp. 614–615.See Sedgewick's web exercises for Algorithms, 4th ed., exercises 5 and 12 (retrieved 2013-01-30).