Bellman–Ford-algoritmus

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 Sablon:Harvard citations 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.Sablon:Sfnp 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.Sablon:Sfnp

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 $| V | - 1$ alkalommal, ahol $| V |$ 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 $O (| V | \cdot | E |)$ időben zajlik, ahol $| V |$ és $| E |$ 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 $| V | - 1$ él, az éleket meg kell vizsgálni $| V | - 1$ 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 $| V |$ 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 [0], ..., 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 $O (| V | \cdot | E |)$ 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 E_f 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 $| V | / 2$ -re.^[1]^[2]

Egy újabb fejlesztés, Bannister és Eppstein (2012) által, véletlenszerű permutációval helyettesíti a Yen második fejlesztésében használt csúcsok tetszőleges lineáris sorrendjét. Ez a változás a Yen fejlesztéséhez (amelyben a legrövidebb út élei szigorúan váltakoznak a két E _f és E _b részhalmaz között), kapcsolódó legrosszabb eset előfordulását valószínűtlenné teszi. Véletlenszerűen permutált csúcs rendezéssel a fő hurokban szükséges iterációk várható száma legfeljebb $| V | / 3$ .^[2]

További algoritmusok

Kínában egy olyan algoritmus, amely egy elsődleges ki- és bejárati sort ad a Bellman–Ford-algoritmushoz, SPFA néven ismert, amelyet Edward Moore 1959-ben tett közzé, és 1994-ben Fanding Duan fedezte fel újra, népszerű azoknál a hallgatóknál, akik részt vesznek a Nemzeti Informatikai Olimpia a Tartományok és a Nemzetközi Egyetemi Programozási Versenyen.

Jegyzetek

Sablon:Jegyzetek

Források

Fordítás

Sablon:Fordítás

↑ Cormen et al., 2nd ed., Problem 24-1, pp. 614–615.
↑ ^2,0 ^2,1 See Sedgewick's web exercises for Algorithms, 4th ed., exercises 5 and 12 (retrieved 2013-01-30).

[1] Cormen et al., 2nd ed., Problem 24-1, pp. 614–615.

[Sedweb-2] 2,0 ^2,1 See Sedgewick's web exercises for Algorithms, 4th ed., exercises 5 and 12 (retrieved 2013-01-30).

[1]

[2]

Bellman–Ford-algoritmus

Tartalomjegyzék

A helyesség igazolása

Negatív körök keresése

Alkalmazások az útválasztásban

Fejlesztések

További algoritmusok

Jegyzetek

Források

Fordítás

Navigációs menü

Bellman–Ford-algoritmus

A helyesség igazolása

Negatív körök keresése

Alkalmazások az útválasztásban

Fejlesztések

További algoritmusok

Jegyzetek

Források

Fordítás

Navigációs menü

Keresés