Legrövidebb utat kereső algoritmusok Adott gráfban szeretnénk egkeresni két pont között a legrövidebb utat (a két pont ’távolsága’ érdekel). Ezt úgy fogjuk tudni megtenni, hogy közben megkapjuk az összes pont egy adott ponttól vett távolságát, ezért erre az átalánosabb esetre keresünk algoritmust. Nem túl nehéz megadni egy ilyet, pl. keressük meg a gráfban az összes utat, válasszuk ki közülük azokat, amelyeknek a végpontjai épp megfelelők, ezek közül a legrövidebb nekünk tökéletes. Mindössze az a gond, hogy nagyon sokáig tart végigcsinálni, a zh-n pedig nem biztos, hogy sok szabadidőnk lesz. Ezért a későbbiekben különböző trükköket alkalmazunk a gyorsaság érdekében (de ragaszkodunk hozzá, hogy biztosan a legrövidebb utat kapjuk). Minden algoritmusnál fel kell tennünk, hogy a gráf összefüggő (különben két pont között esetleg nem is találnánk utat). Elvi lehetőség lenne arra, hogy ne csak egyszerű gráfokkal foglalkozzunk, de se a párhuzamos éleknek (őket helyettesíthetjük a minimumukkal) se a hurokéleknek nincs sok értelme.
BFS (szélességi keresés) Alkalmazásánál feltételezzük, hogy a gráf összes éle ’egységnyi hosszú’, egy út hosszát tehát kizárólag a benne szereplő élek száma határozza meg. Az algoritmus lényege: a kiindulópont távolsága (önmagától) legyen 0, a szomszédaié 1, ezek szomszédaié (ha még nem kaptak értéket) 2 stb. A kiindulópont legyen s. Egy adott ponthoz menet közben fel fogjuk jegyezni a nevét (pl. A), az értékét és hogy melyik pontból jutottunk oda (jele pl. q(A)). (Elég lenne csak azt feljegyezni, hogy melyik pontból értük el, én az áttekinthetőség kedvéért fogom most a többi adatot is jegyezni.) Lássunk egy példát: 4. gyakorlat 1. feladat a) Határozzuk meg (lépésenként) a BFS-algoritmussal a legrövidebb utat A-ból az összes csúcsba! Először készítek egy táblázatot: név érték d(i) q(i)
A feladatban az s-pont az A, ennek adatait beírom a táblázatba. Az éppen vizsgált pontot szürke háttér jelzi: név érték d(i) q(i)
A 0 -
Most a feladatom berakni A összes szomszédját, ilyen például B. név érték, d(i) q(i)
A 0 -
B d(A)+1=1 q(B)=A
A 0 -
B d(A)+1=1 A
Azután C-t. név érték, d(i) q(i)
C d(A)+1=1 A
A-nak nincs több szomszédja, úgyhogy mostantól a következő oszlopot vizsgáljuk: név érték, d(i) q(i)
A 0 -
B d(A)+1=1 A
C d(A)+1=1 A
B olyan szomszédait kell beírni, amik még nincsenek benn, pl. D-t. név A B C D érték, d(i) 0 d(A)+1=1 d(A)+1=1 d(B)+1=2 q(i) A A B (Itt a q már B-lesz, az érték pedig B értékénél eggyel nagyobb.) Aztán E-t. név érték, d(i) q(i)
A 0 -
B d(A)+1=1 A
C d(A)+1=1 A
D d(B)+1=2 B
E d(B)+1=2 B
Mostmár B összes szomszédja szerepel, úgyhogy lépünk a következőre. név érték, d(i) q(i)
A 0 -
B d(A)+1=1 A
C d(A)+1=1 A
D d(B)+1=2 B
E d(B)+1=2 B
A vizsgált csúcs minden szomszédja szerepel, tehát ismét lépünk a következőre. név érték, d(i) q(i)
A 0 -
B d(A)+1=1 A
C d(A)+1=1 A
D d(B)+1=2 B
E d(B)+1=2 B
D-nek van egy szomszédja, ami még nem szerepel, ez pedig F. Őt berakjuk. név érték, d(i) q(i)
A 0 -
B d(A)+1=1 A
C d(A)+1=1 A
D d(B)+1=2 B
E d(B)+1=2 B
F d(D)+1=3 D
D d(B)+1=2 B
E d(B)+1=2 B
F d(D)+1=3 D
D d(B)+1=2 B
E d(B)+1=2 B
F d(D)+1=3 D
D d(B)+1=2 B
E d(B)+1=2 B
F d(D)+1=3 D
D-nek most már szerepel az összes szomszédja, tehát lépünk. név érték, d(i) q(i)
A 0 -
B d(A)+1=1 A
C d(A)+1=1 A
E-nek szerepel az összes szomszédja, tehát lépünk. név érték, d(i) q(i)
A 0 -
B d(A)+1=1 A
C d(A)+1=1 A
F-nek szerepel az összes szomszédja, tehát lépünk. név érték, d(i) q(i)
A 0 -
B d(A)+1=1 A
C d(A)+1=1 A
Nincs több vizsgálandó pont, tehát befejeződött az algoritmus. Eredmények: -
Minden pont A-tól való távolsága szerepel az érték mezőben. Bármelyik ponthoz meg tudjuk adni az utat a következő módon: kiválasztjuk a pontot, ami minket érdekel, pl. F. Először felírjuk a vizsgált pontot, majd a q-ját, ezután annak a q-ját és így tovább, egészen addig, amíg s-hez (itt A) nem érünk: F, D, B, A. Ezt megfordítva megvan a kívánt út: A, B, D, F, amiről tudjuk, hogy ennél rövidebb nem létezik.
Megjegyzések: -
Ha nem kerül be az összes csúcs, akkor a gráf nem volt összefüggő. Ettől függetlenül a gráf adott pontjából (s) elérhető pontokra a legrövidebb utakat kapjuk. Irányított gráf esetén is alkalmazható, ilyenkor a legrövidebb irányított utakat kapjuk.
Élsúlyozott esetek Sajnos nincs mindig olyan szerencsénk, hogy az élek száma jelöli az utak hosszát. Előfordulhat, hogy egy élen ’nehezebb’ végigmenni, mint valamelyik másikon. Ekkor minden élhez egy számot rendelünk, ez lesz az adott él hossza (l(e)). Az út hossza az őt alkotó élek hosszának összege lesz. Ilyen esetben a korábbi algoritmusunk nyilvánvalóan tökéletesen alkalmatlan, hiszen az a legkevesebb élből álló utakat keresi. Kénytelenek vagyunk más eszközökhöz folyamodni. Az alapötlet a következő: A kiindulópont értéke legyen 0, a többié pedig végtelen. Kiválasztunk egy élt, ami mentén javítani szeretnénk. Ha az él kezdőpontjának plusz az élnek az értéke kisebb, mint a végpont értéke, akkor a végpont értékét lecserélhetjük erre az összegre. Ha már semelyik élen nem tudunk javítani, akkor készen vagyunk. A művészet itt az lesz, hogy milyen sorrendben válasszunk éleket úgy, hogy a legkevesebb javításra legyen szükség.
Dijkstra algoritmusa Feltételezzük, hogy nincsen negatív hosszúságú él. Ebben az algoritmusban minden élen legfeljebb egyszer kell elvégezni a javítást. Maga az algoritmus a következő: Készítsünk két halmazt, S-t és T-t. Az S-be kerüljön s, T-be a többi pont. d(s) legyen 0, minden más pontra d(i) legyen végtelen. u0 lesz a mindenkori kitüntetett pontunk, kezdetben ez legyen s. Végezzük el a javítást minden u0-ból valamelyik T-beli pontba vezető élre. A T-beli pontok közül azt, amelyiknek a legkisebb az értéke tegyük át S-be, és nevezzük most őt u0-nak. Mindezt addig ismételjük, amíg T ki nem ürül. Az algoritmus helyességének bizonyítása olvasható a könyvben. Én az alkalmazását szeretném egy példán bemutatni: 4. gyakorlat 1. feladat b) Határozzuk meg (lépésenként) Dijkstra algoritmusával a legrövidebb utat B-ből az összes csúcsba! S={B} T={A;C;D;E;F} u0=B név érték d(i)
A ∞
B 0
C ∞
D ∞
E ∞
F ∞
Az élek, amiken javítást kell végezni, az u0-ból (most B) valamelyik T-beli csúcsba vezetnek. Ilyenek: BA, BC, BE, BD élek. BA: l(e)=3, d(B)=0, d(A)= ∞ ha d(A)>l(e)+d(B) tehát A értéke most 3 lesz, a javítás szükséges volt.
akkor
d(A)
legyen
l(e)+d(B)
A többi élre hasonlóan: BC: javítás szükséges, d(C)=4 BE: javítás szükséges, d(E)=5 BD: javítás szükséges, d(D)=2 Így a táblázat: S={B} T={A;C;D;E;F} u0=B név érték d(i)
A 3
B 0
C 4
D 2
E 5
F ∞
A T-beli pontok közül a legkisebb értéke a D-nek van, tehát átkerül az S-be, és mostantól őt figyeljük: S={B;D} T={A;C;E;F} u0=B név érték d(i)
A 3
B 0
C 4
D 2
E 5
F ∞
A javításhoz szóbajövő élek: DC, DE, DF (DB nem, hiszen nem T-beli pontba vezet) DC: javítás szükséges, d(C)=3 DE: javítás szükséges, d(E)=3 DF: javítás szükséges, d(F)=6
[ d(C)>l(DC)+d(D), hiszen 4>1+2 ] [ d(E)>l(DE)+d(D), hiszen 5>1+2 ] [ d(F)>l(DF)+d(D), hiszen ∞>4+2 ]
Tehát a jelenlegi állás: S={B;D} T={A;C;E;F} u0=B név érték d(i)
A 3
B 0
C 3
D 2
E 3
F 6
Most több legkisebb közül választhatunk (ne feledjük, hogy csak a T-beli pontok jönnek szóba), mindegy, hogy melyket. Én például A-t. S={B;D;A} T={C;E;F} u0=B név érték d(i)
A 3
B 0
C 3
D 2
A javításhoz szóbajövő élek: AC (AB nem, hiszen B már az S-ben van) AC: javítás nem szükséges
[ d(C)
E 3
F 6
A táblázat tehát változatlan: S={B;D;A} T={C;E;F} u0=B név érték d(i)
A 3
B 0
C 3
D 2
E 3
F 6
C 3
D 2
E 3
F 6
C 3
D 2
E 3
F 6
E 3
F 6
Megint legkisebbet választunk, én mondjuk C-t. S={B;D;A;C} T={E;F} u0=B név érték d(i)
A 3
B 0
Szóbajövő élek: CE CE: javítás nem szükséges Így ismét nem változott a helyzet: S={B;D;A;C} T={E;F} u0=B név érték d(i)
A 3
B 0
Most már egyértelműen kell legkisebbet választanom, ez pedig E. S={B;D;A;C;E} T={F} u0=B név érték d(i)
A 3
B 0
C 3
D 2
Szóbajövő élek: EF EF: javítás szükséges, d(F)=5
[ d(F)>l(DF)+d(E), hiszen 6>3+2 ]
A táblázat: S={B;D;A;C;E} T={F} u0=B név érték d(i)
A 3
B 0
C 3
D 2
Most az utolsó F-et is átrakjuk S-be, és mivel T kiürült, megállunk. Eredmények: -
Minden pontra megkaptuk a B-től vett távolságát
E 3
F 5
Megjegyzések -
Irányított élekkel hasonlóan működik. Amelyik pont értéke ∞ marad, az külön komponensben van (vagy irányított esetben nem érhető el irányított úton).
Negatív súlyú élek Eddig feltételeztük, hogy minden él hosszúsága nemnegatív. Mi a helyzet akkor, ha megengedünk ilyen éleket is? Irányítatlan esetben ebből semi jó nem lesz, hiszen egy élen oda-vissza a végtelenségig csökkenthetnénk egy csúcs értékét. Irányított gráfoknál is előfordulhat ilyen, ha van bennük negatív összsúlyú irányított kör. Viszont ezek kizárásával értelmes a feladat.
Ford algoritmusa Feltesszük, hogy nincs a gráfban negatív összsúlyú irányított kör. Az algoritmus alapja az előzőhöz hasonló, a kezdőpont értékül 0-t, minden más pont végtelent kap. A korábbihoz hasonló módon éleken fogunk javítani, azonban itt már nem vagyunk olyan szerencsések, hogy egy élen legfeljebb egyet kelljen javítanunk. Az élek között lerögzítünk egy sorrendet és minden ciklusban ebben a sorrendben próblunk javítani az éleken. Amikor már egy körben egyik élen sem tudtunk javítani, akkor végeztünk. Nézzünk egy konkrét példát: 4. gyakorlat 2. feladat Határozzuk meg (lépésenként) a Ford-algoritmussal a legrövidebb utat Aból az összes csúcsba! Először a táblázat: név érték d(i)
A 0
B ∞
C ∞
Most lerögzítjük az élek közötti sorrendet: A piros számok jelzik, hogy milyen sorban fogom végrehajtani a javításokat.
D ∞
E ∞
1. kör: 1 él: lehet javítani – d(B)=1 név érték d(i)
A 0
B 1
C ∞
D ∞
E ∞
B 1
C 4
D ∞
E ∞
B 1
C 4
D 1
E ∞
B 1
C 4
D 1
E 5
B 1
C 4
D 1
E 2
B 1
C 4
D -1
E 2
B 1
C 4
D -1
E 1
2 él: lehet javítani – d(C)=4 név érték d(i)
A 0
3 él: lehet javítani – d(D)=1 név érték d(i)
A 0
4 él: lehet javítani – d(E)=5 név érték d(i)
A 0
5 él: lehet javítani – d(E)=2 név érték d(i)
A 0
6 él: nem lehet javítani 7 él: lehet javítani – d(D)=-1 név érték d(i)
A 0
8 él: nem lehet javítani 9 él: lehet javítani – d(E)=1 név érték d(i)
A 0
10 él: nem lehet javítani Az első körrel végeztünk, de mivel ebben a körben végeztünk javításokat (nem is keveset), kell tennünk még egy kört.
2. kör: 1 él: nem lehet javítani 2 él: nem lehet javítani 3 él: nem lehet javítani 4 él: nem lehet javítani 5 él: nem lehet javítani 6 él: nem lehet javítani 7 él: nem lehet javítani 8 él: nem lehet javítani 9 él: nem lehet javítani 10 él: nem lehet javítani Ebben a körben nem végeztünk javítást, tehát az agoritmusunk végzett. A végeredmény a legutóbbi táblázatból leolvasható. Most összesen csak két kört kellett tennünk, ezért joggal érezhetjük magunkat szerencsésnek, hiszen a szükséges ciklusok száma akár v+1 is lehet (v a csúcsok száma). Megjegyzések: -
Ha az algoritmus nem ér véget v+1 ciklus alatt, akkor biztosak lehetünk abban, hogy van a gráfban negatív összsúlyú irányított kör (ilyenkor soha nem ér véget az algoritmus). A szükséges ciklusok száma függhet az élek megszámozásától is.
