| dbo:abstract
|
- A Bellman–Ford-algoritmus egy algoritmus, amely kiszámítja egyetlen forrástól (vertex) 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 grafikonok kezelésére, amelyekben az egyes élsúlyok negatív számok. Az algoritmust először Alfonso Shimbel 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. 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. függvény BellmanFord(list vertices, list edges, vertex source) is ::distance[], predecessor[] // Ez a megvalósítás egy gráfba kerül, mint // csúcsa gráf ok és élek listái és két sort tölt meg // (távolság és előd) a legrövidebb útról // a forrástól minden egyes csúcshoz. // 1. lépés: gráf inicializálás for each vertex v in vertices do distance[v] := '''inf''' // A távolság minden csúcshoz történő inicializálása a végtelenig predecessor[v] := '''null''' // És van egy null elődjeőddel distance[source] := 0 // A távolság a forrástól önmagához természetesen nulla // 2. Lépés: az élek ismétlődő lazítása '''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: a negatív súlyú ciklus ellenőrzése '''for each''' edge (u, v) '''with''' weight w '''in''' edges '''do''' '''if''' distance[u] + w < distance[v] '''then''' '''error''' "A gráf negatív súlyú ciklust tartalmaz” '''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 ciklus 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 ciklus létezik a gráfban. (hu)
- A Bellman–Ford-algoritmus egy algoritmus, amely kiszámítja egyetlen forrástól (vertex) 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 grafikonok kezelésére, amelyekben az egyes élsúlyok negatív számok. Az algoritmust először Alfonso Shimbel 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. 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. függvény BellmanFord(list vertices, list edges, vertex source) is ::distance[], predecessor[] // Ez a megvalósítás egy gráfba kerül, mint // csúcsa gráf ok és élek listái és két sort tölt meg // (távolság és előd) a legrövidebb útról // a forrástól minden egyes csúcshoz. // 1. lépés: gráf inicializálás for each vertex v in vertices do distance[v] := '''inf''' // A távolság minden csúcshoz történő inicializálása a végtelenig predecessor[v] := '''null''' // És van egy null elődjeőddel distance[source] := 0 // A távolság a forrástól önmagához természetesen nulla // 2. Lépés: az élek ismétlődő lazítása '''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: a negatív súlyú ciklus ellenőrzése '''for each''' edge (u, v) '''with''' weight w '''in''' edges '''do''' '''if''' distance[u] + w < distance[v] '''then''' '''error''' "A gráf negatív súlyú ciklust tartalmaz” '''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 ciklus 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 ciklus létezik a gráfban. (hu)
|
