Forgalomirányítási algoritmusok matematikai alapjai

összeállította: Tőke Pál

2003. szeptember 12.

Megjegyzés: A következőkben használt gráfelméleti alapfogalmak a DNS gráfok c. anyagban találhatók. Az orientált és az irányított gráfok között nem teszünk különbséget és csak irányított gráfokról beszélünk. Szimmetrikus irányított (orientált) élek tehát megengedettek. Valamely G = (N , A) gráf csúcsainak számát N-nel, éleinek számát A-val jelöljük.

Tétel: Legyen G = (N , A) összefüggő gráf és legyen S az N valamely valódi részhalmaza. Létezik legalább egy olyan (i, j) ∈ A) él, amely kimenő S-ből, azaz amelyre i ∈ S és j ∉ S.

Bizonyítás:

q.e.d.

Definíció: A G′ = (N′, A′) gráf a G = (N , A) gráf részgráfja, ha N′ ⊆ N és A′ ⊆ A.

Definíció: A fa olyan összefüggő gráf, amelyben nincsen kör. Valamely G gráf feszítő fája G olyan részgráfja, amely fa és G minden csúcsát tartalmazza.

Legyen G = (N , A) tetszőleges összefüggő gráf. A G egy lehetséges részgráfjának megalkotásához tekintsük a következő algoritmust:

1. Legyen n tetszőleges csúcs N -ből. Legyen N′ = {n} és A′ = {}.

2. Ha N = N′, akkor álljunk meg, különben folyatás 3.-tól.

3. Legyen (i, j) olyan él, amelyre i ∈ N′ és j ∈ N \ N′.

Legyen

N′ := N′ ∪ {j}
A′ := A′ ∪ {(i, j)}.

Folytatás 2.-től.

Tétel: Tetszőleges összefüggő G = (N , A) gráf esetén a fenti algoritmus a G egy feszítő fáját eredményezi.

Bizonyítás:

q.e.d.

Következmény: Valamely N csúcsból álló összefüggő G gráfhoz mindíg van N − 1 élt tartalmazó feszítő fa.

Következmény: Ha a G = (N , A) gráf összefüggő, akkor A ≥ N − 1.

Következmény: A G összefüggő gráf akkor és csak akkor fa, ha A = N − 1.

Minimális súlyú feszítő fa

Legyen G = (N , A) összefüggő gráf. Tegyük fel, hogy minden (i, j) ∈ A élhez hozzá van rendelve egy w_{ij} valós szám, amelyet az (i, j) él súlyának nevezünk. Konstruáljunk meg G-hez egy olyan feszítő fát, amelyben az élekhez tartozó súlyok összege minimális a lehetséges feszítő fákat tekintve. Az ilyen feszítő fát minimális súlyú feszítő fának nevezzük.

Definíció: Valamely M minimális súlyú feszítő fa tetszőleges részfáját töredéknek (fragment) nevezzük.

Tétel: Legyen F egy tetszőleges töredék, legyen α = (i, j) minimális súlyú F -ből kimenő él. Az F′ = F ∪ ({j}, {(i, j)}) szintén töredék.

Bizonyítás:

q.e.d.

A fenti tétel alapul szolgálhat valamely minimális súlyú feszítő fa megalkotásához.

Prim-Dijkstra féle algoritmus: Induljunk ki egy tetszés szerinti csúcsból. Definíció szerint ezen egyetlen csúcsból álló gráf szükségképpen töredék. Bővítsük ki ezt lépésenként további csúcsokkal és élekkel az előző tétel szerint. Ilyen módon mindíg töredékhez jutunk, ami N lépés után az összes csúcsot tartalmazni fogja, ezért ez utóbbi már minimális súlyú feszítő fa.

A gyakorlati alkalmazások szempontjából fontosak azok az algoritmusok, amelyek esetén egyidejűleg egyszerre több töredék bővitését is megtehetjük.

Kruskal algoritmus: Tegyük fel, hogy egyetlen minimális súlyú feszítő fa létezik. Legyenek F_{1}, F_{2}, ..., F_{n} diszjunkt töredékek (az egyes töredékek csúcsainak hamazai páronként diszjunktak). Bővítsük ki párhuzamosan az egyes töredékeket a fenti tételnek megfelelően a minimális súlyú kimenő élekkel és azok végpontjával. Ilyen módon újra a töredékek egy páronként diszjunkt F′_{1}, F′_{2}, ..., F′_{m} halmazához jutunk. Az algoritmust addig folytathatjuk, amíg egyetlen olyan töredékhez nem jutunk, amely az összes csúcsot tartalmazza. Ez a töredék szükségképpen az egyetlen minimális súlyú feszítő fa.

A Kruskal algoritmusban a bővítések természetesen aszinkron módon is végrehajthatók.

Tétel: Ha minden w_{ij} súly külőnbőző, akkor csak egyetlen minimális súlyú feszítő fa létezik.

Bizonyítás:

q.e.d.

Legrövidebb út

Legyen a továbbiakban G = (N , A) irányított gráf. A G = (N , A) irányított gráfhoz hozzárendelhetjük azt a G′ = (N′, A′) irányítatlan gráfot, amelyre N′ = N és (i, j) ∈ A′ akkor és csak akkor, ha (i, j) ∈ A vagy (j, i) ∈ A.

A G = (N , A) irányított gráfban egy váltakozóan csúcsokból és élekből álló (v_{0}, x_{1}, v_{1}, ...v_{n−1}, x_{n}, v_{n}) sorozat láncolat, nyílt, illetve zárt láncolat, lánc, egyszerű lánc vagy út, ciklus, egyszerű ciklus vagy kör, ha megfelelően láncolat, nyílt, illetve zárt láncolat, lánc, egyszerű lánc vagy út, ciklus, egyszerű ciklus vagy kör a G′ = (N′, A′) irányítatlan gráfban.

A G = (N , A) irányított gráfban egy váltakozóan csúcsokból és élekből álló (v_{0}, x_{1}, v_{1}, ...v_{n−1}, x_{n}, v_{n}), n ≥ 0, sorozatot irányított láncolatnak nevezünk, ha a sorozat csúccsal kezdődik és végződik, továbbá, ha minden a sorozatban előforduló x_{i} élre, i = 1, 2, ..., n, x_{i} = (v_{i−1}, v_{i}). Tetszőleges irányított láncolat megadásához tehát elegendő megadni a benne előforduló csúcsok (v_{0}, v_{1}, ...v_{n−1}, v_{n}) rendezett sorozatát. A zárt, illetve nyílt irányított lácolat, az irányított lánc, az egyszerű irányított lánc vagy irányított út és az irányított ciklus fogalmai analóg módon származtathatók a DNS gráfok fejezetben leirtaknak megfelelően. Valamely (v_{0}, x_{1}, v_{1}, ...v_{n−1}, x_{n}, v_{n}) zárt irányított láncolatot egyszerű irányított ciklusnak, vagy irányított körnek nevezünk, ha a v_{1}, ..., v_{n} csúcsok mind különbözőek és n ≥ 2.

A G = (N , A) irányított gráf erősen összefüggő, ha bármely két csúcsa összeköthető irányított úttal.

Legyen a G = (N , A) irányított gráf erősen összefüggő, és tegyük fel, hogy minden (i, j) ∈ A élhez hozzá van rendelve egy d_{ij} valós szám, amelyet az (i, j) él általánosított hosszának nevezhetünk (bár d_{ij} nem szükségképpen nem negatív). A következőkben az általánosított hossz helyett a hossz megjelölést használjuk. Tetszőleges p = (i, j, k, ..., l, m) G-beli irányított út esetén, legyen a p hossza: d(i, j, k, ..., l, m) = d_{i,j} +d_{j,k} +...+d_{l,m}. A legrövidebb út probléma úgy fogalmazható meg, hogy határozzuk meg a G irányított gráfban tetszőleges két különböző csúcs között a legrövidebb irányított utat.

A következőkben a G irányított gráf valamely generikus 1 címkéjű csúcsát tekintjük és az 1 csúcs és az összes i ≠ 1 csúcs közötti i-ből az 1-be vezető legrövidebb irányított út meghatározásával foglalkozunk. Ez a probléma ekvivalens azzal a problémával, hogy határozzuk meg az összes i ≠ 1 csúcshoz az 1-ből ez i be vezető legrövidebb irányított utat. Ha ugyanis az első feldathoz van megoldás, akkor a G irányított gráf minden élének irányítását fordítsuk meg a súlyok változatlanul hagyása mellett. Ha erre a gráfra alkalmazzuk a megoldást, akkor könnyen látható, hogy ha a kapott irányított utakban szereplő összes irányított élek irányítását megfordítjuk, akkor éppen a második probléma megldását kapjuk. Tehát az egyik feladatot a másik duálisának tekinthetjük.

Definíció: Azt mondjuk, hogy a G irányított gráfban a D részgráf irányítás, ha a D tetszőleges i csúcshoz pontosan egy az i-ből az 1-be vezető irányított utat tartalmaz.

Definíció: Azt mondjuk, hogy a G irányított gráfban a D részgráf duális irányítás, ha a D tetszőleges i csúcshoz pontosan egy az 1-ből az i-be vezető irányított utat tartalmaz.

Tétel: Teteszőleges D irányítás forrásfüggetlen, azaz bármely i csúcsra az i-be bemenő, valamely csúcsot az 1 csúccsal összekökő a D-hez tartozó irányított utak i utáni közvetlen folytatása (az i ből kimenő irányított él) független az irányított utak kezdetétől.

Bizonyítás:

q.e.d.

Tétel: Teteszőleges D irányítás esetén, ha (n_{k} = i, n_{k−1}, , ..., n_{0} = 1) a D-hez tartozó tetszőleges irányított út, akkor minden j = 0, 1, ..., k-ra az (n_{j}, , ..., n_{0} = 1) a D-hez tartozó, az n_{j}-t az 1-gyel összekötő irányított út.

Bizonyítás:

q.e.d.

Tétel: Teteszőleges D duális irányítás esetén, ha (n_{0} = 1, , n_{1}, ..., n_{k} = i) a D-hez tartozó tetszőleges irányított út, akkor minden j = 0, 1, ..., k-ra az (n_{0} = 1, ..., n_{j}) a D-hez tartozó, az 1-et az n_{j}-vel összekötő irányított út.

Bizonyítás:

q.e.d.

A következőkben a Bellman-Ford, a Dijkstra valamint a Floyd-Warshall algoritmusokat tekintjük át a legrövidebb irányított utakból álló irányítás, illetve duális irányítást meghatározásához. A Bellman-Ford algoritmus optiális irányítást határoz meg valamely tetszőlegesen választott rendeltetési pont felé. A Dijkstra algoritmus optiális duális irányítást határoz meg valamely tetszőlegesen választott rendeltetési pontból kiindulva. A Floyd-Warshall algoritmus az összes lehetséges különböző csúcspár esetén határozza meg az őket összekötő legrövidebb irányított utakat. Nincs olyan ismert módszer, amely csak valamely i és j csúcsok között határozza meg a legrövidebb irányított utat. Ahhoz, hogy az i és j csúcsok között meghatározzuk a legrövidebb irányított utat, meg kell határozni az i és az összes többi csúcs között a legrövidebb irányított utat!

Valamely irányítás meghatározásához természetesen más, elsősorban fokozatosan kiépítő algoritmusok is léteznek. Ezekbe az algoritmusokba politikai jellegű döntések is beépíthetők.

Bellman-Ford algoritmus

Tegyük fel, hogy valamely csúcshoz az 1 címkét rendeltük és az összes csúcsból ezen csúcsba vezető minimális hosszúságú irányított utak meghatározása a feladat úgy, hogy ezek az utak egy D irányítást alkossanak.

Tegyük fel továbbá, hogy bár a d_{ij} távolságok lehetnek negatívak is, de tetszőleges irányított kör hossza nem negatív. A jelölések egyszerűsítése érdekében tegyük fel, hogy d_{ij} = ∞, ha (i, j) ∉ A.

Jelölje D_{i}^{(h)} azon i-ből az 1 csúcsba vezető irányított utak hosszának minimumát, amelyek legfeljebb h élet tartalmaznak. Ha ilyen irányított út nincs, akkor legyen D_{i}^{(h)} = ∞. Könnyen látható, hogy D_{1}^{(h)} = 0 minden h ≥ 0 esetén.

Tétel: Kezdetben

D_{i}^{(0)} = ∞, minden i ≠ 1

Minden h ≥ 0-ra,

D_{i}^{(h+1)} = min_{j≠i}[d_{ij} + D_{j}^{(h)}] minden i ≠ 1

Bizonyítás: Legyen i ≠ 1 tetszőleges csúcs és legyen h tetszőleges nem negatív egész szám. Tegyük fel, hogy nem létezik i-ből az 1-be vezető, legfeljebb h + 1 élt tartalmazó irányított út. Ekkor az értelmezés szerint D_{i}^{(h+1)} = ∞. Legyen j tetszőleges i-től különböző csúcs. A D_{j}^{(h)} és a d_{ij} mindegyike nem lehet véges, hiszen ebből az következne, hogy az (i, j) éle a G irányított gráfnak és létezik a j-ből az1-be vezető, legfeljebb h élet tartalmazó irányított út. Könnyen látató, hogy ekkor létezik

az i-ből az 1-be vezető, legfeljebb h + 1 élet tartalmazó irányított út is, ami ellentmondáshoz vezet. Ezért

min_{j≠i}[d_{ij} + D_{j}^{(h)}] = ∞

tehát

D_{i}^{(h+1)} = min_{j≠i}[d_{ij} + D_{j}^{(h)}]

teljesül.

Tegyük fel, hogy létezik az i-ből az 1-be vezető legfeljebb h + 1 élt tartalmazó irányított út. Ebből következik, hogy D_{i}^{(h+1)} véges és azon j ≠ i csúcsok N′(i) halamaza, amelyekre igaz, hogy létezik legfeljebb h élet tartalmazó a j-ből az 1-be vezető irányított út és a (i, j) él a G irányított gráfban, biztosan nem üres. Legyen (i, k, ..., 1) D_{i}^{(h+1)} hosszúságú, legfeljebb h + 1 élet tartalmazó irányított út, amely az i-ből az 1-be vezet. Mivel a (k, ..., 1) út a k-ból az 1-be vezet és legfeljebb h élet tartalmaz, ezért

D_{i}^{(h+1)} ≥ d_{ik} + D_{k}^{(h)} ≥ min_{j∈N′(i)}[d_{ij} + D_{j}^{(h)}] = min_{j≠i}[d_{ij} + D_{j}^{(h)}]

Legyen k′ ∈ N′(i) olyan index, amelyre

min_{j∈N′(i)}[d_{ij} + D_{j}^{(h)}] = d_{ik′} + D_{k′}^{(h)}

Legyen továbbá (k′, ..., 1) olyan legfeljebb h élet tartalmazó irányított út, amely hossza pontosan D_{k′}^{(h)}. Tekintsük az (i, k′, ..., 1) irányított láncolatot. Ha ez nem irányított út, mert az i csúcs előfordul az (k′, ..., 1) irányított út mentén (csak egyszer fordulhat elő!), akkor tekintsük az (k′, ..., 1) irányított útnak az i csúcstól vezető (i, k′′, ..., 1) részét, amely nyilván irányított út és legfeljebb h + 1 élet tartalmaz. Ekkor mivel az (i, k′, ..., i) irányitott kör és a feltevések szerint ezen kör hossza nem negatív, továbbá a (k′′, ..., 1) irányított út nyilván legfeljebb h élet tartalmaz, ezért

min_{j∈N′(i)}[d_{ij} + D_{j}^{(h)}] = d(i, k′, ..., 1) ≥ d(i, k′′, ..., 1) ≥ d_{ik′′} + D_{k′′}^{(h)} ≥ min_{j∈N′(i)}[d_{ij} + D_{j}^{(h)}]

Innen adódik, hogy a (k′′, ..., 1) irányított út hossza D_{k′′}^{(h)} és

min_{j∈N′(i)}[d_{ij} + D_{j}^{(h)}] = d_{ik′′} + D_{k′′}^{(h)}

Tehát mindíg választhatunk olyan k′ ∈ N′(i) csúcsot, amlyre

min_{j∈N′(i)}[d_{ij} + D_{j}^{(h)}] = d_{ik′} + D_{k′}^{(h)}

és létezik olyan (k′, ..., 1) irányított út, amely hossza D_{k′}^{(h)} és az (i, k′, , ..., 1) is irányított út. Mivel ez utóbbi út legfeljebb h + 1 élből áll és hossza d_{ik′} + D_{k′}^{(h)}, ezért

min_{j≠i}[d_{ij} + D_{j}^{(h)}] = min_{j∈N′(i)}[d_{ij} + D_{j}^{(h)}+] = d_{ik′} + D_{k′}^{(h)} ≥ D_{i}^{(h+1)}

Tehát a tétel állítása igaz. q.e.d.

Tetszőleges irányított út legfeljebb N − 1 élt tartalmaz, ezért h ≥ N − 1 esetén D_{i}^{(h)} = D_{i}, ahol D_{i} az i-ből az 1-be vezető legrövidebb irányított út hossza. Kiindulva tehát a fenti kezdeti értékekből és alkalmazva a tételben szereplő összefüggéseket, N − 1 lépés után a legrövidebb irányított utak hosszát kapjuk eredményül. A legrövidebb irányított út meghatározásához ezt az algoritmust Bellman-Ford algoritmusnak nevezzük.

A fenti tétel alapján, a tétel feltételei mellett a D_{i} értékek kielégítik a következő összefüggéseket:

D_{i} = min_{j≠i}[d_{ij} + D_{j}] minden i ≠ 1
D_{1} = 0

Ezeket az egyenleteket Bellman egyenleteknek nevezzük. A Bellman egyenletek azt fejezik ki, hogy a legrövidebb irányított út hossza az i csúcstól az 1 csúcsig egyenlő az utolsó irányított él hossza plusz a legrövidebb irányított út hossza az i-t megelőző csúcstól az 1 csúcsig .

Ha ismerjük a Bellman-Ford algoritmus alapján kapott D_{i} értékeket, amelyek a Bellman egyenletek megoldásai és feltesszük, hogy tetszőleges az 1 csúcsot nem tartalmazó irányított kör hossza pozitív, akkor egyszerűen megkonstruálhatunk olyan irányított utakat is, amelyek a legrövidebbek tetszőleges i és az 1 vonatkozásában. Tetszőleges i ≠ 1 csúcs esetén tekintsünk egy olyan j csúcsot, ahol a D_{i} értékekre vonatkozó Bellman egyenletekben a minimum eléretik. Tekintsük minden i ≠ 1-re az így kivásztott (i, j) élt. Egyszerűen belátható, hogy tetszőleges i-ből kiindúlva a kiválasztott élek mentén visszafelé a már érintett csúcsok nem ismétlődhetnek meg az irányított körök hosszára tett megszorítás miatt. Ha ilyen ismétlődés létezne, akkor ezen irányított bejárás biztosan tartalmazna irányított kört. Legyen (k, m, ..., n, k) egy ilyen irányított kör. Mivel a kiválasztás szerint

D_{i} = d_{ij} + D_{j} minden i ≠ 1

ezért

D_{k} = d_{km} + ... + d_{nk} + D_{k}

adódna, ami ellentmondás, mivel a k, m, ..., n, k zárt irányított kör az 1 pontot nem tartalmazhatja, mert az 1 pontból nem indul ki egyetlen kiválasztott irányított él sem és ezért a feltétel szerint d_{km} + ... + d_{nk} > 0.

A fentiekből következik, hogy bármely i ≠ 1 csúcsból legfeljebb N − 1 lépés után az 1 pontba jutunk. Az igy kiválasztott irányított út hossza tetszőleges i esetén nyiván D_{i}. Könnyen látható, hogy az így kiválasztott részgráfra igaz, hogy tetszőleges i esetén pontosan egy az i-ből az 1-be vezető irányított minimális hosszúságú utat tartalmaz, tehát irányítás az 1 felé.

Tétel: Ha tetszőleges az 1 csúcsot nem tartalmazó irányított kör hossza pozitív, akkor a Bellman egyenleteknek egyetlen megoldása létezik.

Bizonyítás: Legyen D̃_{i}, i = 1, 2, ..., N, a Bellman egyeneletek egy tetszőleges megoldása. Legyenek D_{i}^{(0)} a Bellman-Ford algoritmus kezedeti értékei. Ekkor

D̃_{i} ≤ D_{i}^{(0)} i = 1, 2, ..., N

nyilván teljesül. Ebből viszont következik, hogy

D̃_{i} ≤ D_{i}^{(h)} i = 1, 2, ..., N

is teljesül minden h ≥ 0 esetén. Ha ugyanis az állítás igaz valamely h ≥ 0 és i = 1, 2, ..., N esetén, akkor

D̃_{i} = min_{j≠i}[d_{ij} + D̃_{j}] ≤ min_{j≠i}[d_{ij} + D_{j}^{(h)}] = D_{i}^{(h+1)} i ≠ 1

is igaz (monotonitási tulajdonság!),

D̃_{1} ≤ D_{1}^{(h+1)}

pedig nyilvánvalóan teljesül. Az előzőek szerint

D_{i}^{(N−1)} = D_{i} i = 1, 2, ..., N

ahol D_{i} az i csúcsból az 1 csúcsba vezető legrövidebb irányított út hosszát jelöli. Ezért

D̃_{i} ≤ D_{i} i = 1, 2, ..., N

Felhasználva, hogy minden az 1 csúcsot tartalmazó irányított kör hossza pozitív, tetszőleges i ≠ 1 csúcshoz megadható egy olyan az i-ből az 1-be vezető irányított út, amely hossza pontosan D̃_{i}. Ezért

D̃_{i} ≥ D_{i} i = 1, 2, ..., N

is teljesül. Mivel D̃_{i}, i = 1, 2, ..., N, tetszőleges megoldás volt, ezért valóban egyetlen megoldás létezik. q.e.d.

Módosított Bellman-Ford algoritmus

A következőkben a Bellman-Ford algoritmus című fejezet fogalmait és jelöléseit használjuk. Tegyük fel, hogy a G = (N , A) gráf csúcsainak N halmaza két diszjunkt N_{1} és N_{2} halmaz egyesítéseként áll elő. Valamely i csúcsot valamely j csúccsal összekötő irányított út megengedett, ha legfeljebb csak az irányított út végpontjai nem N_{1} halmazhoz tartozóak. Tegyük fel, hogy a G = (N , A) gráf tetszőleges két csúcsa összeköthető megengedett irányított úttal.

Ez a módosított modell megfelel valamely TCP/IP típusú számítógépes hálózat hálózati rétege modelljének, ahol az N_{1} csúcshalmaz azon hostok halmazának felel meg, amelyek képesek tranzit forgalmat kezelni. Az ilyen hostokat a forgalomirányítás szempontjából routereknek nevezzük. A másik N_{2} csúcshalmaz azon hostoknak felel meg, amelyek nem képesek tranzitforgalom kezelésére. A TCP/IP hálózati architektúrában a hálózati réteg entitásainak ezt a két típusát élesen meg kell különbözteni. A hálózati réteg gráf modelljében a csúcsoknak a hálózati réteg entitásai, azaz a hostok felelnek meg. Az i és a j csúcsok között akkor és csak akkor létezik irányított él, ha létezik olyan fizikai alhálózat, amelyhez az i-nek, illetve a j-nek megfelelő host valamely IP címmel azonosított host-interfészen keresztül közvetlenül csatlakozik. A lehetséges forgalomirányításoknak megfelelő modellekben nyiván csak megengedett irányított utak fordulhatnak elő.

Felmerül a kérdés, hogy alkalmazható-e a Bellman-Ford algoritmus valamely kitüntetett 1 rendeltetési pont felé, a d_{i,j} súlyozásnak megfelelő minimális hosszúságú megengedett irányított utakat tartalmazó irányítás meghatározására. Tegyük fel, hogy tetszőleges irányított kör hossza, amelyben minden csúcs N_{1} halmazhoz tartozó, nem negatív.

Jelölje D_{i}^{(h)} azon i-ből az 1 csúcsba vezető megengedett irányított utak hosszának minimumát, amelyek legfeljebb h élet tartalmaznak. Ha ilyen út nincs, akkor legyen D_{i}^{(h)} = ∞. Megegyezés szerint legyen D_{1}^{(h)} = 0 minden h ≥ 0 esetén.

Tétel: Kezdetben

D_{i}^{(0)} = ∞, minden i ≠ 1

Minden egymásután következő h ≥ 0-ra,

D_{i}^{(h+1)} = min_{j≠i és j∈N_{1}∪{1}}[d_{ij} + D_{j}^{(h)}] minden i ≠ 1

Bizonyítás: A tétel bizonyítása az előző fejezet megfelelő tételének bizonyításához analóg módon végezhető el. q.e.d.

Tetszőleges megengedett irányított út legfeljebb N_{1} −1+2 élt tartalmaz, ahol N_{1} a N_{1} halmaz elemeinek számát jelöli. Ezért h ≥ N_{1} − 1 + 2 esetén D_{i}^{(h)} = D_{i}, ahol D_{i} az i-ből az 1-be vezető legrövidebb megengedett irányított út hossza. Kiindulva tehát a fenti kezdeti értékekből és alkalmazva a tételben szereplő összefüggéseket, N_{1} − 1 + 2 lépés után a legrövidebb megengedett irányított utak hosszát kapjuk eredményül.

A fenti tétel alapján a D_{i} értékek kielégítik a következő Bellman egyenleteket:

D_{i} = min_{j≠i és j∈N_{1}∪{1}}[d_{ij} + D_{j}] minden i ≠ 1
D_{1} = 0

Ha ismerjük a fenti algoritmus alapján kapott D_{i} értékeket, és feltesszük, hogy tetszőleges az 1 csúcsot nem tartalmazó, csak az N_{1} halmazhoz tartozó csúcsokat tartalmazó irányított kör hossza pozitív, akkor az előző fejezetben megismert módon egyszerűen megkonstruálhatjuk magukat a megengedett legrövidebb irányított utakat is úgy, hogy azok egy irányítást alkossanak.

Érvényes a következő unicitás tétel is.

Tétel: Ha tetszőleges az 1 csúcsot nem tartalmazó, csak az N_{1} halmazhoz tartozó csúcsokat tartalmazó irányított kör hossza pozitív, akkor a Bellman egyenleteknek egyetlen megoldása létezik.

Bizonyítás: A tétel bizonyítása szintén az előző fejezet megfelelő tétele bizonyításához ananlóg módon történhet. q.e.d.

I. Alkalmazás

Tekintsünk a következőkben olyan (fizikai) hálózatot, ahol minden host egyetlen közös átviteli közeghez kapcsolódik. Az ilyen kapcsolódást multipont kapcsolatnak, magát a hálózatot pedig multipont hálózatnak nevezik. Nyilvánvaló, ha az ilyen átviteli közegen valamely két kapcsolódó host közötti adatátvitel megjelenik, akkor az minden kapcsolódó host csatlakozási pontjánál is megjelenik és a host számára leolvashatóvá válik. A multipont kapcsolat több fizikai hálózati szabványba is beépült. Ezek közül a legelterjedtebb az ETHERNET fizikai hálózati szabvány. Fontos kiemelni azt a nyilvánvaló tényt, hogy a multipont hálózatok esetében az átviteli közegre továbbított adat minden csatlakozó hostnál pontosan egy példányban jelenik meg. A multipont hálózatok területileg lokális hálózatok (Local Area Networks - LAN). Tekintettel arra, hogy a multipont hálózatok térbeli kiterjedése korlátozott, felmerül az igény a multipont hálózatok összekapcsolására. Ha két multipont hálózatnak van egy vagy több közös kapcsolódó hostja, akkor egy ilyen host alkalmas lehet a két multipont hálózat közötti adatforgalom közvetítésére. Ez azt feltételezi, hogy további, az adatátvitel közvetítését biztosító funkciókat valósítsunk meg ezeken hostokon. Az ilyen adatátvitel közvetítésére felkészített hostokat a következőkben switcheknek (kapcsolóknak) nevezzük. Ez a látszólag egyszerű probléma akkor válik bonyolulttá, ha megköveteljük, hogy az így kialakított úgynevezett kiterjesztett multipont hálózatra (extended LAN-ra) is teljesüljön: ha egy adat mejelenik valamelyik komponens multipont hálózat átviteli közegén, akkor a multipont hálózatokból álló hálózat tetszőleges multipont hálózatának tetszőleges hostjához pontosan egy példányban kell eljutnia a szóbanforgó adatnak. Ennek megvalósítása a switchek közötti alkalmas együttműködést (protokollt) feltételez. Egy ilyen lehetséges protokollnak a matematikai alapja a Bellman-Ford algoritmus.

Legyen G = (N , A) összefüggő irányított gráf, ahol N = R∪H Tegyük fel, hogy R ≠ ∅, H ≠ ∅ és R ∩ H = ∅. Nevezzük az R halmaz elemeit switcheknek vagy routereknek, a H halmaz elemeit hálózati csúcsoknak. Tegyük fel, hogy a G gráfban tetszőleges (i, j) irányított él vagy R-hez tartozó csúcsot köt össze H-hoz tartozó csúccsal, vagy H-hoz tartozó csúcsot köt össze R-hez tartozó csúccsal. Tegyük fel továbbá, hogy tetszőleges (i, j) ∈ A él esetén a (j, i) ∈ A is teljesül.

Származtassuk a G = (N , A) gráf alapján a következő \overline{G} = (\overline{N} , \overline{A}) általánosított irányított gráfot. Legyen \overline{N} = R, legyen továbbá \overline{A} az összes olyan rendezett (i, j, k) hármasokból álló halmaz, ahol i, k ∈ R és (i, j) ∈ A, valamint (j, k) ∈ A. Az (i, j, k) él és az i, valamint a k csúcsok illeszkednek.

Tegyük fel, hogy minden i ∈ R csúcshoz hozzá van rendelve egy id_{i} természetes szám, amelyet a csúcs azonosítójának nevezünk. Tegyük fel, hogy különböző csúcsokhoz különböző természetes számok vannak rendelve.

Olyan osztott algoritmus kialakítása a cél, amely minden i ∈ R csúcsnál meghatározza, hogy az R halmaz elemeihez rendelt azonosítók közül melyik a legkisebb, meghatározza a minimális azonosítójú csúcsnak a szóbanforgó csúcstól való távolságát, és minden i ∈ R csúcshoz egyúttal meghatározza és megjegyzi annak az (i, j, k) élnek az (i, j) kiinduló részét is, amely a szóbanforgó csúcsból a minimális azonosítójú csúcsba vezető olyan irányított út része, amely a két csúcs vonatkozásában minimális hoszúságú. Ha több ilyen (i, j, k) él is van, akkor az algoritmus a szóbanforgó csúcsnál ezek közül önkényesen kiválaszt egyet és regisztrálja annak (i, j) kiinduló részét. Nevezzük ezt a kiinduló részt i ∈ R csúcsból kimenő R jellegű megjegyzett portnak. Legyen kezdetben minden i ∈ R csúcsnál a minimális azonosítóra vonatkozó kiinduló becslés a csúcs saját azonosítója és így önmagától, mint a minimális azonosítójú csúcstól a távolsága 0. Az algoritmus szerint tehát minden csúcs kezdetben saját azonosítóját tekinti minimálisnak a rendelkezésre álló lokális információk alapján. A kialakítandó algoritmus azon alapul, hogy az egyes i ∈ R csúcsok a lehetséges (i, j, k) ∈ \overline{A}) élek mentén átadják egymásnak a minimális azonosítóra vonatkózó pillanatnyi becsült értékeiket, valamint ezen becsült értékkel mint azonosítóval azonosított csúcsnak a szóbanforgó csúcstól való távolságra vonatkózó pillanatnyi becsült értékeiket. Ennek alapján a fogadó csúcsok újraértékelik a minimális azonosítóra és az ezen azonoítóval azonosított csúcsnak a szóbanforgó fogadó csúcstól való távolságára vonatkozó becsléseiket és a kapcsolatos megjegyzett kimenő irányokat.

Feltesszük továbbá, ha valamely i ∈ R és j ∈ H-ra (i, j) ∈ A, akkor ha az i ∈ R csúcs valamely (i, j, k) él mentén információt ad át a k ∈ R csúcsnak, akkor ez az információ tetszőleges olyan k′ ∈ R csúcshoz is eljut, amelyre (i, j, k′) ∈ \overline{A}. Ebből következik, hogy tetszőleges j ∈ H elemre mindazon i ∈ R elemek, amelyekre (i, j) ∈ A, ki tudják választani, hogy közülük mely i′ ∈ R csúcs van a legközelebb a legkisebb azonosítójú csúcshoz. Ha több ilyen csúcs is van, akkor ezek közül a legkisebb azonosítójút kell kiválasztatni minden érintett csúcsnál az adott j ∈ H vonatkozásában. Az így kiválasztott i′ ∈ R csúcsnál az (i′, j) kiinduló irányt meg kell jegyezni. Nevezzük ezt a kimenő irányt H jellegű megjegyzett portnak.

Az elmondottakból következik, hogy a minimális azonosítójú i ∈ R csúcsnál nem lesz R jellegű kimenő port. Ugyanakkor, ha ezen csúcs szerepel valamely (i, j, k) ∈ \overline{A} élben, akkor (i, j) kimenő irány biztosan H jellegű megjegyzett port lesz i-nél.

Ha a fenti algoritmus szinkron módon hajtódik végre, azaz minden i ∈ R csúcs egyidőben adja át a minimumra és a távolságra vonatkozó becsléseit az öszes lehetséges (i, j, k) ∈ \overline{A} él mentén a k ∈ R csúcsoknak és ezzel egyidőben történik az egyes csúcsoknál az új becslések és a kapcsolatos R jellegű megjegyzett portok újraértékelése, valamint minden j ∈ H elemekre a megfelelő H jellegű megjegyzett port meghatározása a fentiek szerint alkalmas i′ ∈ R csúcsnál, akkor bizonyítható a Bellman-Ford algoritmus bizonyításához hasonló gondolatmenet szerint, hogy az algoritmus stabilizálódik, azaz alkalmas számú lépés után az egyes csúcsoknál az értékek már nem változnak, amiből következik hogy a valóságos minimális azonosító érték, valamint ezen minimális azonosítójú csúcstól való valóságos távolság regisztrálódik az egyes csúcsoknál az ennek megfelelő megjegyzett R és esetleg még további H jellegű kimenő portokkal együtt.

Térjünk vissza a kiinduló G = (N , A) irányított összefüggő gráfhoz és minden a fenti algoritmus szerinti regisztrált R jellegű megjegyzett portot és H jellegű megjegyzett portot, mint éleket vegyünk csak figyelembe a szimmetrikus élpárjaikkal együtt. A csúcsok halmaza legyen változatlan. Legyen az így nyert részgráf G′ = (N′, A′). A G′ részgráfra igaz a következő: ha egy adat valamely j ∈ H csúcsnál a hálózatba kerül, tehát minden olyan i ∈ R csúcshoz továbbítódik, amelyre (i, j) ∈ A′, akkor, ha az összes ilyen i csúcs minden az (i, j) kimenő élétől különböző kimenő éle mentén továbbítja az adatot a megfelelő hálózatba, és ez az algoritmus ismétlődik ezekben és a további hálózati csúsokban is amíg csak lehetséges, akkor a szóbanforgó adat minden hálózati csúcshoz pontosan egy példányban jut el.

Megjegyzés: Belátható, ha a G′ gráfban a szimmetrikus élpárokat egyetlen irányítatlan éleknek tekintjük, akkor az igy nyert gráf fa lesz.

Dijkstra algoritmus

Legyen a G = (N , A) irányított gráf erősen összefüggő. Tekintsük a G irányított gráf valamely generikus 1 címkéjű csúcsát és határozzuk meg a G valamely P részgráfját úgy, hogy bármely i csúcs esetén a P pontosan egy az 1-ből az i-be vezető irányított utat tartalmazzon és ez az út minimális hosszúságú legyen az 1-ből az i-be vezető irányított utak között. A továbbiakban tegyük fel, hogy minden él hossza pozitív. Ha (i, j) ≠ A, akkor legyen d_{ij} = ∞. A Dijkstra-féle algoritmus gondolata, hogy keressük meg a legrövidebb irányított utakat ezen utak hosszának sorrendjében. Először tehát keressük meg a legrövidebb legrövidebb irányított utat, azután a második legrövidebb legrövidebb irányított utat, stb.

Tegyük fel, hogy már eljutottunk valamely P = (N′, A′) részgráfig, amelyre igaz, hogy tetszőleges N′-beli csúcs közelebb van 1-hez, mint tetszőleges nem N′- beli csúcs. Tegyük fel továbbá, hogy minden N′-beli i csúcs esetén ismerjük az 1-től az i csúcsba vezető legrövidebb irányított út D_{i} hosszát és az A′ minden N′-beli i ≠ 1 csúcsra egyetlen olyan irányított élet tartalmaz, amely i-be mutat és ez az irányított él egy olyan az 1-ből az i-be vezető irányított út utolsó irányított éle, amely hossza a minimális D_{i}. Minden nem N′-beli i csúcs esetén pedig ismerjük azon irányított utak D_{i} minimális hosszát, amelyek az 1-ből az i-be vezetnek és amelyek mentén csak az i nem N′-beli csúcs és véges D_{i} esetén ismerjük egy ilyen, minimális D_{i} hosszúságú irányított út utolsó i-be mutató élét. Jelölje e_{i} az algoritmus folyamán az i-hez ismert élet, ha ilyen él létezik. Belátható, hogy a P = (N′, A′) részgráf tetszőleges i csúcsa esetén pontosan egy az 1-ből az i-be vezető irányított utat tartalmaz és ezen út hossza a minimális D_{i}.

Ha N′-n kívül még van csúcs, akkor vegyük hozzá P -hez azt P -hez nem tartozó i csúcsot, amelyre a D_{i} a legkisebb N \ N′ halmazban, az i-hez ismert éllel együtt. Ezen i pont esetén könnyen belátható, hogy D_{i} véges és D_{i} egyúttal az 1-ből az i-be vezető legrövidebb irányított út hossza is megszorítás nélkül és a hozzá ismert e_{i} él egy ilyen minimális D_{i} hosszúságú út utolsó i-be mutató éle.

Az algoritmus részletesen a következő:

\underline{Első iteráció:} Legyen P = \{N′, A′\}, amelyre

N′ = {1}, A′ = ∅ D_{1} = 0

Legyen minden j ≠ 1-re:

D_{j} = d_{1j} és (e_{j} = (1, j) ha d_{1j} ≠ ∞)

Vége az iterációs lépésnek.

\underline{Minden további iteráció:} Ha N′ már minden csúcsot tartalmaz, akkor iterációs lépésnek vége. Ha nem, akkor keressünk meg egy olyan i ∉ N′ csúcsot, amelyre

D_{i} = min_{j∉N′} D_{j}

Legyen

P = {N′ ∪ {i}, A′ ∪ {e_{i}}}

Minden j ∉ N′-re legyen

ha D_{i} + d_{ij} < D_{j} akkor e_{j} = (i, j) és
D_{j} = min[D_{j}, D_{i} + d_{ij}]

Vége az iterációs lépésnek.

Tétel:Tetszőleges n természetes számra, ha a G = (N , A) gráfon a fenti iterációs lépéseket az első iterációs lépéstől kezdődően n-szer egymásután végrehajtjuk, akkor G egy olyan P = (N′, A′) részgráfjához jutunk, amelyre igazak a következők: Tetszőleges N′-beli csúcs közelebb van 1-hez, mint tetszőleges nem N′-beli csúcs.

Minden N′-beli i csúcs esetén D_{i} az 1-től az i csúcsba vezető legrövidebb irányított út hossza. Az A′ minden N′-beli i ≠ 1 csúcsra egyetlen olyan irányított élet tartalmaz, amely i-be mutat és ez az irányított él egy olyan az 1-ből az i-be vezető irányított út utolsó irányított éle, amely hossza a minimális D_{i}. Minden nem N′-beli i csúcs esetén D_{i} azon irányított utak minimális hossza, amelyek az 1-ből az i-be vezetnek és amelyek mentén csak az i nem N′-beli csúcs és véges D_{i} esetén e_{i} egy ilyen, minimális D_{i} hosszúságú út utolsó i-be mutató éle. A P = (N′, A′) részgráf tetszőleges i csúcsa esetén pontosan egy az 1-ből az i-be vezető irányított utat tartalmaz és ezen út hossza a minimális D_{i}.

Bizonyítás: A bizonyítás a végrehajtott iterációs lépések száma szerinti teljes indukcióval történik. Legyen n = 1. Az algoritmus alapján ekkor P = (N′, A′) = ({1}, ∅). A D_{1} = 0 valóban az 1 csúcsot az 1 csúccsal összekötő irányított utak minimális hossza, továbbá tetszőleges 1-től különböző csúcsok, amelyek a N′ halmaz kiegészítő halmazát képezik, a d_{ij} > 0 feltételből adódóan mind az 1 pontnál távolabb vannak az 1-ponttól. Mivel az 1-ből az 1-be vezető minimális hosszúságú irányított út egyetlen élet sem tartalmaz, így a P = (N′, A′) részgráf tetszőleges i csúcsa esetén pontosan egy az 1-ből az i-be vezető irányított utat tartalmaz és ezen út hossza minimális D_{i}. A D_{j} = d_{1j} értékek minden j ∉ N′ esetén azon irányított utak minimális hosszát jelentik, amelyek az 1 csúcsot kötik össze a j csúccsal úgy bennük minden csúcs N′-beli, kivéve az utolsó j csúcsot. Minden j ∉ N′ csúcsra az e_{j} irányított él akkor és csak akkor létezik, ha létezik olyan irányított út, amely az 1 csúcsból a j csúcsba vezet, amely mentén csak a j csúcs nem N′-beli. Ha ilyen út létezik, akkor e_{j} ezen utak közül egy minimális D_{j} hosszúságú útnak az utolsó i-be mutató éle.

Tegyük fel, hogy valamely n természetes számra a tétel állítása igaz. Végezzük el az iterációs lépéseket n-szer az első iterációs lépéstől kezdődően. Ha a P gráf a G gráf összes csúcsát már tartalmazza, akkor az n + 1-edik iterációs lépés már semmit sem változtat meg, tehát az indukciós feltevés miatt az állítás igaz n + 1re is. Tegyük fel, hogy a végrehajtott n iterációs lépés után van olyan csúcs a gráfban, amely még nem eleme a N′ halmaznak. Bővítsük ki a P gráfot az i csúccsal és az e_{i} éllel a fenti algoritmus szerint. Hasonlóan, módosítsuk a D_{j}, illetve e_{j} értékeket a fenti algoritmus szerint, ha van még csúcs a gráfban amely nem eleme a N′ ∪{i} halmaznak. D_{i} minimális tulajdonsága miatt az 1 csúcsot az i-vel összekötő minimális hosszúságú irányított utak olyan tulajdonságúak, hogy az i csúcson kívül csak N′-beli csúcsot tartalmaznak. Ezért D_{i} az 1-ből az i-be vezető irányított utak minimális hosszát jelenti és minden más k, N′-hez nem tartozó, i-től különböző csúcs esetén az 1-ből a k-ba vezető irányított utak minimális hossza nem kisebb, mint D_{i}. Ha a kininduló P gráfra igaz volt, hogy tetszőleges i csúcsa esetén pontosan egy irányított utat tartalmaz, amely 1-ből az i-be vezet és ennek az irányított útnak a hossza minden i-re a minimális D_{i}, akkor könnyen látható, hogy az eredményül kapott P gráfra is igaz, hogy tetszőleges i csúcsa esetén pontosan egy irányított utat tartalmaz, amely 1-ből az i-be vezet és ennek az irányított útnak a hossza minden i-re a minimális D_{i}. Az indukciós feltevésből kiidulva és az új D_{j} értékek kiszámítási szabálya szerint, ezek a D_{j} értékek tetszőleges j ∉ N′ ∪ {i} csúcsra azon 1-ből a j-be vezető irányított utak minimális hosszával egyenlők, amelyek a j csúcsot kivéve mind N′ ∪ {i}-hez tartozóak. Tetszőleges j ∉ N′ csúcsra az e_{j} irányított él akkor és csak akkor létezik, ha létezik olyan irányított út, amely az 1 csúcsból a j csúcsba vezet és amely mentén csak a j csúcs nem N′-beli és e_{j} egy ilyen, minimális D_{i} hosszúságú irányított út utolsó, j-be mutató éle. Ezért abból a feltevésből, hogy a tétel állítása igaz n-re, következett, hogy igaz n + 1-re is. Tehát a tétel állítása igaz.

q.e.d.

Következmény: A fenti algoritmus szerint a P részgráfba a csúcsok az 1-től mért távolságuk növekvő sorrendjéban kerülnek. N iterációs lépés után meghatározott D_{i} érték minden i csúcs esetén az 1-ből az i-be vezető minimális hosszúságú irányított út hosszával egyenlő. Az algoritmus N iterációs lépés után egy olyan P részgráfot eredményez, amely tetszőleges i csúcs esetén pontosan egy irányított utat tartalmaz, amely 1-ből az i-be vezet és ennek az irányított utnak a hossza minden i-re a minimális D_{i}. Ezért a P részgráf egy minimális utakat tartalmazó duális irányítást képez az 1 csúcs vonatkozásában.

I. Megjegyzés:A Dijkstra algoritmus alkalmas módosításával minden i ≠ 1 pontra meghatározhatjuk az összes az 1-ből az i-be vezető minimális hosszúságú irányított utat.

Tekintsük a következő módosított algoritmust:

\underline{Első iteráció:} Legyen P = \{N′, A′\}, amelyre

N′ = {1}, A′ = ∅ D_{1} = 0

Legyen minden j ≠ 1-re:

D_{j} = d_{1j}
és (e_{j} = {(1, j)} ha d_{1j} ≠ ∞ és e_{j} = ∅ ha d_{1j} = ∞)

Vége az iterációs lépésnek.

\underline{Minden további iteráció:} Ha N′ már minden csúcsot tartalmaz, akkor iterációs lépésnek vége. Ha nem, akkor keressünk meg egy olyan i ∉ N′ csúcsot, amelyre

D_{i} = min_{j∉N′} D_{j}

Legyen

P = {N′ ∪ {i}, A′ ∪ e_{i}}

Minden j ∉ N′-re legyen

ha D_{i} + d_{ij} = D_{j} és D_{j} < ∞ akkor e_{j} = e_{j} ∪ {(i, j)},
ha D_{i} + d_{ij} < D_{j} akkor e_{j} = {(i, j)} ,
ha D_{i} + d_{ij} > D_{j} akkor e_{j} változatlan és
D_{j} = min[D_{j}, D_{i} + d_{ij}]

Vége az iterációs lépésnek.

II. Megjegyzés: Forgalomirányítási szempontból valamely i ≠ 1 pont vonatkozásában nem az összes az 1-ből az i-be vezető minimális hosszúságú irányított út teljes ismeretére van szükség, hanem ezen utaknak a kezdetét kell ismerni az 1 pontban. Szükséges tehát meghatároznunk valamely i ≠ 1 pont vonatkozásában azokat az 1-ből kiinduló irányított éleket, amelyek ezen irányított utak kezdő élei. Jelölje \underline{e}_{i} ezeknek az élek halmazát tetszőleges i ≠ 1 pontra. Használva az előző megjegyzésben szereplő algoritmus fogalmait és jelöléseit, az \underline{e}_{i} meghatározásához szükség van az e_{i} halmazok meghatározására is. A Dijkstra algoritmus alábbi módosításával az \underline{e}_{i} halmazok meghatározhatók.

Tekintsük a következő módosított algoritmust:

\underline{Első iteráció:} Legyen P = \{N′, A′\}, amelyre

N′ = {1}, A′ = ∅ D_{1} = 0

Legyen minden j ≠ 1-re:

D_{j} = d_{1j} és
(e_{j} = \underline{e}_{j} = \{(1, j)\} ha d_{1j} ≠ ∞ és
e_{j} = \underline{e}_{j} = ∅ ha d_{1j} = ∞)

Vége az iterációs lépésnek.

\underline{Minden további iteráció:} Ha N′ már minden csúcsot tartalmaz, akkor iterációs lépésnek vége. Ha nem, akkor keressünk meg egy olyan i ∉ N′ csúcsot, amelyre

D_{i} = min_{j∉N′} D_{j}

Legyen

P = \{N′ ∪ \{i\}, A′ ∪ e_{i}\} és \underline{e}_{i} =( ⋃_{(k,i)∈e_{i} és k≠1} \underline{e}_{k})⋃( ⋃_{(k,i)∈e_{i} és k=1}\{(1, i)\})

ha D_{i} + d_{ij} = D_{j} és D_{j} < ∞ akkor e_{j} = e_{j} ∪ {(i, j)},
ha D_{i} + d_{ij} < D_{j} akkor e_{j} = {(i, j)} ,
ha D_{i} + d_{ij} > D_{j} akkor e_{j} változatlan és
D_{j} = min[D_{j}, D_{i} + d_{ij}]

Vége az iterációs lépésnek.

III. Megjegyzés: Csoportos (multicast)forgalomirányításnál fontos eldönteni valamely i_{0} csúcs szerepét. Legyen M a csúcsok valamely részhalmaza. Építsük ki a Dijkstra algoritmus iterációs lépéseivel a P részgráfot mindaddíg, amíg az összes M-beli csúcs fel nem kerül a P gráfba, és minden iterációs lépésnél jegyezzük fel az \underline{e}_{i}^{i_{0}} halmazba azokat az éleket, amelyekhez van olyan az 1-ből az i-be vezető minimális hosszúságú irányított út, amely tartalmazza a illető élet és ez az él az i_{0} csúcsból indul ki. A szükséges iterációs lépések elvégzése után az ⋃_{k∈M} \underline{e}_{k}^{i_{0}} halmaz határozza meg az i_{0} csúcs szerepét az 1 csúcsból az M csoporthoz történő csoportos irányításnál. Ha az 1 csúcsból az M csoportnak megfelelő multicast címre továbbított datagram az e_{i_{0}} él mentén érkezik az i_{0} csúcshoz, akkor az i_{0} csúcsnak minden az ⋃_{k∈M} \underline{e}_{k}^{i_{0}} halmazhoz tartozó kimenő él mentén továbbítania kell a datagramot. A Dijkstra algoritmus megfelelő módosítása a következő:

\underline{Első iteráció:} Legyen P = \{N′, A′\}, amelyre

N′ = {1}, A′ = ∅ D_{1} = 0

Legyen minden j ≠ 1-re:

D_{j} = d_{1j} és
(e_{j} = \underline{e}_{j}^{i_{0}} = \{(1, j)\} (ha d_{1j} ≠ ∞ és i_{0} = 1),
e_{j} = \{1, j\}, \underline{e}_{j}^{i_{0}} = ∅ (ha d_{1j} ≠ ∞ és i_{0} ≠ 1),
e_{j} = \underline{e}_{j} = ∅ ha d_{1j} = ∞)

Vége az iterációs lépésnek.

\underline{Minden további iteráció:} Ha N′ már minden csúcsot tartalmaz, akkor iterációs lépésnek vége. Ha nem, akkor keressünk meg azt a legkisebb indexű i ∉ N′ csúcsot, amelyre

D_{i} = min_{j∉N′} D_{j}

Legyen

P = \{N′ ∪ \{i\}, A′ ∪ e_{i}\} és \underline{e}_{i}^{i_{0}} =( ⋃_{(k,i)∈e_{i} és k≠i_{0}} \underline{e}_{k}^{i_{0}})⋃( ⋃_{(k,i)∈e_{i} és k=i_{0}}\{(i_{0}, i)\})

ha D_{i} + d_{ij} < D_{j} akkor e_{j} = {(i, j)} és

D_{j} = min[D_{j}, D_{i} + d_{ij}]

Vége az iterációs lépésnek.

Az e_{j} (mindig egyelemű!) élhalmazok meghatározása más algoritmus szerint is történhet.

Floyd-Warshall algoritmus

Ez az algoritmus az előző kettőtől eltérően minden i és j csúcspár esetén meghatározza az i-ből a j-be vezető legrövidebb irányított út hosszát. Hasonlóan a Bellman-Ford algoritmushoz, tegyük fel, hogy az irányított élek hossza lehet negatív is, de bármely irányított kör hossza nem negatív.

A gráfban előforduló csúcsokat jelöljük rendre 1, 2, ..., N-nel. Legyen D_{ij}^{(n)} azon legrövidebb irányított út hossza, amely az i csúcsból a j csúcsba vezet és legfeljebb az 1, 2, ..., n csúcsokat tartalmazza.

Tétel: A D_{ij}^{(n)} értékere igazak a következő összefüggések:

D_{ij}^{(0)} = d_{ij} minden i, j i ≠ j

n = 0, 1, 2, ..., N − 1-re

D_{ij}^{(n+1)} = min[D_{ij}^{(n)}, D_{i(n+1)}^{(n)} + D_{(n+1)j}^{(n)}] minden i ≠ j

Bizonyítás:

q.e.d.

A fenti tétel alapján a D_{ij}^{(N)} = D_{ij}, az i-ből a j csúcsba vezető minimális hosszúságú irányított út hossza N számú iterációs lépés után adódik.

Osztott aszinkron Bellman-Ford algoritmus

Legyen G = (N , A) irányított gráf, amely erősen összefüggő. Tekintsünk egy forgalomirányító algoritmust, amely a legrövidebb irányított út mentén továbbítja a csomagokat a forrásponttól a rendeltetési pontig. Valós körülmények között az élek hossza változhat részint azért, mert ezek a kapcsolatok meghibásodhatnak, részint amiatt, hogy olyan mértéket választottunk, amely eredendően időfüggő (pl. várakozó sorok hossza a kimeneteknél, átlagos késleltetési idők a kapcsolatokon, stb). Mindezekből adódóan szükséges időről-időre a legrövidebb irányított utakat újból meghatározni a megváltozott feltételekhez.

A továbbiakban feltesszük, hogy bármely (i, j) él d_{ij} hossza pozitív, és minden i és j különböző csúcspárra, ha (i, j) él, akkor (j, i) is él a gráfban. Elvben nem zárjuk ki, hogy a d_{ij} értékek időben változhatnak. A következőkben azonban a Bellman-Ford algoritmus egy olyan változatát vizsgáljuk meg, ahol a d_{ij} értékek nem változnak, de a kezdeti feltételek viszonylag tág határok között választhatók meg. Ez a modell megfelel a valóságnak, ha a d_{ij} értékekről csupán azt tételezzük fel, hogy valamely t_{0} időpont után már nem változnak. Mivel a d_{ij} értékek a t_{0} időpont előtt változhattak, ezért tetszőleges i csúcs esetén a D_{i} legrövidebb irányított út hossza a legrövidebb irányított úttal együtt, csak közelítő értéknek tekinthető.

A következőkben D_{i} valamely i forráscsúcstól valamely generikus 1 rendeltetési csúcshoz vezető legrövidebb irányított út hosszát jelöli és érdekeltek vagyunk tetszőleges i esetén a D_{i}, valamint az i-ből az 1-be vezető valamely legrövidebb irányított út meghatározásában úgy, hogy ezek az utak egy irányítást alkossanak az 1 csúcs vonatkozásában. A feltételekből következik, hogy a D_{i} értékek megoldják a Bellman egyenleteket:

D_{i} = min_{j∈N(i)}[d_{ij} + D_{j}] minden i ≠ 1
D_{1} = 0

ahol N(i) jelöli az i csúcs környezetét, vagy másképpen azon j csúcsok halmazát, amelyekre az (i, j) létező él.

A Bellman-Ford algoritmust a következöképpen lehet megadni:

D_{i}^{(h+1)} = min_{j∈N(i)}[d_{ij} + D_{j}^{(h)}] i ≠ 1, h ≥ 0
D_{1}^{(h+1)} = 0 h ≥ 0

A konvergencia a legrövidebb irányított úthosszhoz biztosítható, ha a kezdeti feltételekre

D_{i}^{(0)} = ∞ minden i ≠ 1
D_{1}^{(0)} = 0

Az algoritmus párhuzamosítható, mivel az iteráció lépései az egyes csúcsokban egyidejűleg, párhuzamosan hajthatók végre. Az algoritmus egy lehetséges párhuzamosított formája a következő:

Minden csúcs egyidejűleg kiszámítja a (h + 1)-edik közelítés értékét, a kapott eredményt szintén egyidejűleg továbbítja az összes szomszédos csúcs felé, majd a h növelése után a következő közelítés számítható ki az egyes csúcsoknál az egyenleteknek megfelelően. Ha a kezdeti feltételeket a fentiek szerint választjuk meg, akkor legfeljebb N − 1 iterációs lépés után (N a csúcsok száma) az egyes csúcsoknál ismeretesek a D_{i} értékek és a legrövidebb út irányába való elmozdulás.

A gyakorlatban azonban a műveletek egyidejű végrehajtása komoly nehézségekbe ütközik és nehezen egyeztethető az algoritmus elkezdése is.

Megoldást jelentene a problémákra, ha eltekinthetnénk a szigorú szinkronitástól és a kezdeti feltételek előzőekben előírt megválasztásától.

A lehetséges algoritmus a következő műveletek végrehajtását jelentené az egyes csúcsoknál "időről-időre":

D_{i} = min_{j∈N(i)}[d_{ij} + D_{j}]

felhasználva a legutóbbi D_{j} becsléseket, amelyeket az illető csúcs a szomszéd csúcsoktól kapott és a kimenő élek aktuális hosszát. Minden csúcsnál gondoskodni kellene arról is, hogy a legutóbbi D_{i} becslés "időről-időre" eljusson a szomszédos csúcsok mindegyikéhez. Azonban a műveletek szigorúan egyidejű végrehajtását el kellene vetni.

Az aszinkron Bellman-Ford algoritmus megfogalmazásához a következő jelőlések és feltételezések szükségesek.

Minden t időpillanatban rendelkezésre állnak a következők:

D_{j}^{i}(t): Az i csúcsnál a legrövidebb irányított út hosszára vonatkozó becslés minden az i környezetében levő j csúcsra, amely a legutóbbi, a j-től kapott adat.

D_{i}(t): Az i csúcsnál a Bellman-Ford algoritmus szerint a legutóbb kiszámított becslés a legrövidebb irányított út hosszára vonatkozóan.

A legrövidebb irányított út hosszára vonatkozó becslés az 1 csúcsnál

D_{1}(t) = 0 minden t ≥ t_{0}
D_{1}^{i}(t) = 0 minden t ≥ t_{0}, és i-re, amelyre 1 ∈ N(i)

Bármely i csúcs ismeri a d_{ij} kimenő élek hosszát minden j ∈ N(i)-re. A d_{ij} értékek minden (i, j) él esetén pozitívak és a t_{0} időpont után már nem változnak.

Feltesszük továbbá, hogy a legrövidebb irányított út hosszára vonatkozó becslések az egyes csúcsoknál legfeljebb csak a t_{0}, t_{1}, t_{2}, ... időpontokban változnak, ahol a t_{m+1} > t_{m} minden m-re és t_{m} → ∞, ha m → ∞.

Tetszőleges i ≠ 1 csúcsnál a t_{m} időpillanatban a következő események valamelyike következhet be:

1. Az i csúcs új becslést állapít meg a D_{i}(t) értékre

D_{i}(t) = min_{j∈N(i)}[d_{ij} + D_{j}^{i}(t)]

alapján és a D_{j}^{i}(t), j ∈ N(i), értékeket változatlanul hagyja.

2. Az i csúcs egy vagy több szomszédos j ∈ N(i) csúcstól fogadja a D_{j}(t) értéket és felülírja vele a D_{j}^{i}(t) értéket. A többi becslést változatlanul hagyja.

3. Az i csúcsnál nem történik semmi, az i csúcsnál minden becslés változatlan marad.

Legyen T^{i} azon időpontok halmaza a fenti sorozatból, amelyekben az 1.-ben leírt esemény következik be az i csúcsnál és legyen T_{j}^{i} azon időpontok halmaza a sorozatból, amikor az i csúcs új becslést fogad a j csúcstól a 2.-ben leírtaknak megfelelően.

1. Feltétel: A T^{i} és T_{j}^{i} halmazok végtelen számosságúak minden i ≠ 1 és minden j ∈ N(i) esetén. Az egyes csúcsoknál az újabb becslések kiszámítása és a szomszédos csúcsoktól a becslések fogadása soha nem fejeződik be.

2. Feltétel: Minden D_{i}(t_{0}) és D_{j}^{i}(t_{0}), j ∈ N(i), nem negatív. Továbbá nem negatív minden olyan becslés is, amely a t_{0} pilanat előtt lett elindítva, de csak a t_{0} után érkezik meg a rendeltetési helyre.

3. Feltétel: Tetszőleges \overline{t} ≥ t_{0} pillanathoz megadható olyan t̃ ≥ \overline{t}, hogy tetszőleges j csúcsra, azok a D_{j} becslések, amelyek a j csúcsnál lettek kiszámítva a \overline{t} időpont előtt, már egyetlen i csúcsnál, amelyre j ∈ N(i), sem kerülnek fogadásra a t̃ időpont után. A régi legrövidebb út hosszára vonatkozó becslések szükségképpen felülíródnak.

Tétel. Az 1., 2. és a 3. feltételek teljesülése esetén létezik olyan t_{m} időpont amelyre

D_{i}(t) = D_{i}, minden t ≥ t_{m}, i = 1, ..., N

ahol D_{i} az i-ből az 1 csúcsba vezető legrövidebb út hosszának pontos értéke.

Bizonyítás: A bizonyítás alapgondolata, hogy minden i csúcshoz megadhatók olyan \{\underline{D}_{i}^{k}\} és \{\overline{D}_{i}^{k}\} sorozatok, amelyekre

\underline{D}_{i}^{k} ≤ \underline{D}_{i}^{k+1} ≤ D_{i} ≤ \overline{D}_{i}^{k+1} ≤ \overline{D}_{i}^{k}

és

\underline{D}_{i}^{k} = D_{i} = \overline{D}_{i}^{k} elegendően nagy k-ra

A jelzett tulajdoságú sorozatok megalkotsához a Bellman-Ford iteráció következő monotonitási tulajdonságát kell kihasználni. Legyenek \overline{D}_{j} és D̃_{j} olyan értékek, amelyekre

\overline{D}_{j} ≥ D̃_{j} minden j ∈ N(i)

ekkor könnyen látható, hogy

min_{j∈N(i)}[d_{ij} + \overline{D}_{j}] ≥ min_{j∈N(i)}[d_{ij} + D̃_{j}]

Ezekből következik, hogy ha D_{i}^{k} a Bellman-Ford iterációval kapott sorozat valamely D_{i}^{0}, i = 1, 2, ...N kiindulási értékek esetén, amelyre D_{i}^{1} ≥ D_{i}^{0} minden i-re, akkor, akkor D_{i}^{k+1} ≥ D_{i}^{k} minden i-re és k-ra. Hasonlóan, ha D_{i}^{1} ≤ D_{i}^{0} minden i-re, akkor D_{i}^{k+1} ≤ D_{i}^{k} minden i-re és k-ra.

Legyen \overline{D}_{i}^{k} a Bellman-Ford iteráció k-adik lépésében kapott eredmény, ahol a kezdeti feltételekre

D_{i}^{(0)} = ∞ i ≠ 1
D_{1}^{(0)} = 0

Hasonlóan, legyen \underline{D}_{i}^{k} a Bellman-Ford iteráció k-adik lépésében kapott eredmény, ahol a kezdeti feltételekre

D_{i}^{(0)} = 0 i = 1, 2, ..., N

Könnyen látható, hogy a \overline{D}_{i}^{k} és \underline{D}_{i}^{k} sorozatokra teljesül

\underline{D}_{i}^{k} ≤ \underline{D}_{i}^{k+1} ≤ D_{i} ≤ \overline{D}_{i}^{k+1} ≤ \overline{D}_{i}^{k}

A d_{ij} > 0 minden i és j-re feltétel miatt

\overline{D}_{i}^{k} = D_{i} k ≥ N − 1

Igazolni kell, hogy elegendően nagy k-ra \underline{D}_{i}^{k} = D_{i} is teljesül. Teljes indukcióval könnyen igazolható, hogy minden k-ra \underline{D}_{i}^{k} egy olyan i-ből kiinduló irányított láncolat hossza, amely legfeljebb k számú élet tartalmaz. Mivel \underline{D}_{i}^{k} ≤ D_{i} ≤ max_{i} D_{i}, ezért minden k-ra \underline{D}_{i}^{k} legfeljebb

\frac{max_{i} D_{i}}{min_{ij} d_{ij}}

számú él hosszának összege. Mivel az élek halmaza véges, ezért teteszőleges i ≠ 1 esetén a lehetséges \underline{D}_{i}^{k}, k = 0, 1, ..., értékek halmaza véges. A \underline{D}_{i}^{k} sorozat monotonitása miatt, ebből következik, hogy megadható olyan i-től függő \overline{k} küszöb (a küszöböt konstruktíve nem tudjuk megadni!), amelyre ha k ≥ \overline{k}, akkor

\underline{D}_{i}^{k} = \underline{D}_{i}^{k+1}

Mivel a különböző i értékek számossága véges, ezért ilyen \overline{k} küszöb i-től függetlenül is létezik és ezen \overline{k} indexre

\underline{D}\overline{k} ; i = \underline{D}_{i}^{\overline{k}+1} i = 1, 2, ..., N

tehát az \underline{D}\overline{k} ; i értékek megoldják a Bellman-Ford egyenleteket. A már hivatkozott feltevések alapján a megoldás egyértelműsége miatt

\underline{D}_{i}^{k} = D_{i} minden i = 1, 2, ..., N, k ≥ \overline{k}

A tétel állításának bizonyításához elegendő belátni, hogy tetszőleges k ≥ 0 értékhez megadható olyan t(k), hogy minden t-re, amelyre t ≥ t(k)

\underline{D}_{i}^{k} ≤ D_{i}(t) ≤ \overline{D}_{i}^{k}  i = 1, 2, ..., N
\underline{D}_{i}^{k} ≤ D_{j}^{i}(t) ≤ \overline{D}_{i}^{k}  j ∈ N(i), i = 1, 2, ..., N

és minden t-re, amelyre t ∈ T_{j}^{i}, t ≥ t(k)

\underline{D}_{j}^{k} ≤ D_{j}(τ_{j}^{i}(t)) ≤ \overline{D}_{j}^{k} j ∈ N(i), i = 1, 2, ..., N

ahol τ_{j}^{i}(t) jelöli azt a legkésőbbi időpontot amelynél az i-ben rendelkezésre álló D_{j}^{i}(t) a j-ben kiszámításra került.

A bizonyítás teljes indukcióval történik. k = 0 esetén t(0) = t_{0} alkalmas választás a kezdeti értékekre, valamint a t_{0} előtt kiszámított, de csak t_{0} után átadott értékekre tett feltétel miatt. Tegyük fel, hogy az állítás igaz valamely k-ra. Akkor felhasználva a Bellman-Ford iteráció monotonitását, kapjuk, hogy minden t ∈ T^{i} és t ≥ t(k)-ra

\underline{D}_{i}^{k+1} ≤ D_{i}(t) ≤ \overline{D}_{i}^{k+1}

Válasszuk ki minden i = 1, 2, ..., N-re a legkisebb olyan t ∈ T^{i}, amelyre t ≥ t(k) és tekintsük ezek közül a legnagyobbat.Legyen ez az érték t′(k). Ekkor

\underline{D}_{i}^{k+1} ≤ D_{i}(t) ≤ \overline{D}_{i}^{k+1} minden t ≥ t′(k), i = 1, 2, ..., N

Az 1. és 3. feltételek miatt τ_{j}^{i}(t) → ∞ ha t → ∞ minden i és j-re. Válasszuk meg a t(k + 1) ≥ t′(k) értéket úgy, hogy τ_{j}^{i}(t) ≥ t′(k) teljesüljön minden i és j-re. Ekkor minden t ≥ t(k + 1)-re

\underline{D}_{j}^{k+1} ≤ D_{j}^{i}(t) ≤ \overline{D}_{j}^{k+1} minden t ≥ t(k + 1), j ∈ N(i), i = 1, 2, ..., N

és minden t-re, amelyre t ∈ T_{j}^{i}, t ≥ t(k + 1)

\underline{D}_{j}^{k+1} ≤ D_{j}(τ_{j}^{i}(t)) ≤ \overline{D}_{j}^{k+1} j ∈ N(i), i = 1, 2, ..., N

Ezzel a tétel állítása bizonyítást nyert.

q.e.d.