HÁLÓZATOK I. Segédlet a gyakorlati órákhoz Készítette:
10. 2015-16. tanév 1. félév
Göcs László mérnöktanár KF-GAMF Informatika Tanszék
Elosztott forgalomirányítás
Bellman-Ford algoritmus
1. Feladat B 3
A
1
D
3
2
1 C
1. Feladat a, Adja meg a B és C pont Routing tábláját !
B tábla
C tábla
Cél
Next Hop
d
A
A
3
C
D
2
D
D
1
Cél
Next hop
d
A
A
2
B
D
2
D
D
1
1. Feladat b, Az A pont információt cserél B-vel, Bellman Ford algoritmus szerint elkészíti a saját tábláját. A nem tud semmit, csak B-t látja.
C A
B
D
1. Feladat
A tábla
Cél
Next hop
d
B
B
3
C
B
5
D
B
4
C
3 3 A
B
1 1
D
1. Feladat c, Miután az A pont információt cserél B-vel, és C-vel, Bellman Ford algoritmus szerint elkészíti a saját tábláját.
A tábla (csere C-vel)
A tábla (csere B és Cvel)
Cél
Next hop
d
B
C
4
C
C
2
D
C
3
Cél
Next hop
d
B
B
3
C
C
2
D
C
3
2. Feladat
B 2
A
1
D
2
1
1 C
2. Feladat a.) Adja meg a B és a C pont routing tábláját jól és teljesen kitöltve az ábra mellett megadott formában! Mindig a legrövidebb utat válassza!
B tábla
C tábla
Cél
Next hop
d
A
A
2
C
C
2
D
D
1
Cél
Next hop
d
A
A
1
B
B
2
D
D
1
2. Feladat b.) Miután az A pont információt cserél csak B-vel, a Bellman-Ford algoritmus szerint elkészíti a saját tábláját. Adja meg ezt a táblát!
A tábla
Cél
Next hop
d
B
B
2
C
B
4
D
B
3
2. Feladat c.) Miután az A pont információt cserél B-vel és C-vel is, a Bellman-Ford algoritmus szerint elkészíti a saját tábláját. Adja meg ezt a táblát!
A tábla
Cél
Next hop
d
B
B
2
C
C
1
D
C
2
Egy csúcsból a többibe vezető legkisebb költségű út megkeresése Dijkstra algoritmusa
Forrás: Lócsi Levente
Adott: Egy gráf, súlyozott élekkel. (Egy városcsoport, és hogy melyikből melyikbe juthatunk el, és mennyiért.) Vagy mennyibe kerül közéjük építeni egy utat…
Mj.: Vehetünk irányított éleket is. Amennyiben irányítatlan élekkel van dolgunk, úgy képzeljük, hogy az élen mindkét irányban közlekedhetünk.)
Feladat:
Határozzuk meg egy adott csúcsból az összes többibe vezető legkisebb költségű út költségét. Adjuk meg azt is, hogy ezen az optimális úton melyik csúcs előzi meg az aktuális csúcsot. (Ki a szülője?)
Megoldás: (Dijkstra algoritmusa) Először is tegyük fel, hogy mindenhova végtelen nagy költséggel juthatunk csak el; kivéve oda, ahol vagyunk, ahová ingyen eljuthatunk. Majd minden körben válasszuk ki a még nem elintézett csúcsok közül azt, amelyikbe a legolcsóbban tudtunk eljutni. Majd vizsgáljuk meg a szomszédjait, el tudunk-e oda jutni az addiginál kisebb költséggel. (Ábrán: El tudunk-e jutni F-be az eddigi 12-nél olcsóbban? Igen.) Ha igen, módosítsuk ezen szomszéd elérési költségét és szülőjét. Ha nem, hagyjuk békén. Majd ha minden szomszédját megvizsgáltuk, a csúcsot besoroljuk az „elintézett” csúcsok közé. Akkor végeztünk, ha minden csúcsot elintéztünk.
B C
6 3 A 4
1 9
7 5
F
D 1
5
E
8 2
3
G
9
A gráf. Az A csúcsból indulunk.
B
∞
C
6
∞
3 A 4
0
1 9
7 5
D
∞
1
∞G
E
∞
∞
8 2
5
F
3
9
Kiinduló-helyzet Kezdőcsúcsban 0, többiben végtelen érték
B
∞
C
6
∞
3 A 4
0
1 9
7 5
D
∞
1
∞G
E
∞
∞
8 2
5
F
3
9
Válasszuk ki a legolcsóbban elérhető pontot. (A)
Majd vizsgáljuk meg sorra a szomszédait.
B
∞
C
6
∞
3 A 4
0
1 9
7 5
D
∞
1
∞G
E
∞
∞
8 2
5
F
3
9
B: 0 + 3 = 3 < végtelen
B
3
C
6
∞
3 A 4
0
1 9
7 5
D
∞
1
∞G
E
∞
∞
8 2
5
F
3
9
Végtelen helyére 3. A, mint B szülője megjegyezve
B
3
C
6
∞
3 A 4
0
1 9
7 5
D
∞
1
∞G
E
∞
∞
8 2
5
F
3
9
D: 0 + 5 = 5 < végtelen
B
3
C
6
∞
3 A 4
0
1 9
7 5
D
5
1
5
E
F
∞
∞
8 2
∞G
3
9
Végtelen helyére 5. A, mint D szülője megjegyezve
B
3
C
6
∞
3 A 4
0
1 9
7 5
D
5
1
5
E
F
∞
∞
8 2
∞G
3
9
G: 0 + 8 = 8 < végtelen
B
3
C
6
∞
3 A 4
0
1 9
7 5
D
5
1
5
E
F
∞
∞
8 2
3
9
Végtelen helyére 8.
8 G
A, mint G szülője megjegyezve
B
3
C
6
∞
3 A 4
0
1 9
7 5
D
5
1
5
E
F
∞
∞
8 2
3
9
Végeztünk A-val.
8 G
(Nincs több szomszédja)
B
3
C
6
∞
3 A 4
0
1 9
7 5
D
5
1
5
E
F
∞
∞
8 2
3
8 G
9
Válasszuk ki a legolcsóbban elérhető pontot a még nem szürkék közül. (B) Majd vizsgáljuk meg sorra a szomszédait.
B
3
C
6
∞
3 A 4
0
1 9
7 5
D
5
1
5
E
F
∞
∞
8 2
3
9
C: 3 + 6 = 9 < végtelen
8 G
B
3
C
6
9
3 A 4
0
1 9
7 5
D
5
1
5
E
F
∞
∞
8 2
3
9
Végtelen helyére 9.
8 G
B, mint C szülője megjegyezve
B
3
C
6
9
3 A 4
0
1 9
7 5
D
5
1
5
E
F
∞
∞
8 2
3
9
F: 3 + 9 = 12 < végtelen
8 G
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
12
5
1
5
E
∞
8 2
3
9
Végtelen helyére 12.
8 G
B, mint F szülője megjegyezve
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
12
5
1
5
E
∞
8 2
3
9
D: 3 + 4 = 7 > 5
8 G
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
12
5
1
5
E
∞
8 2
3
8 G
9
Ez az út (ABD) tehát nem jobb, mint az eddig D-be vezető út. (AD)
D szülője marad A.
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
12
5
1
5
E
∞
8 2
3
9
Végeztünk B-vel.
8 G
(Nincs több szomszédja)
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
12
5
1
5
E
∞
8 2
3
8 G
9
Válasszuk ki a legolcsóbban elérhető pontot a még nem szürkék közül. (D) Majd vizsgáljuk meg sorra a szomszédait.
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
12
5
1
5
E
∞
8 2
3
9
C: 5 + 7 = 12 > 9
8 G
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
12
5
1
5
E
∞
8 2
3
8 G
9
Ez az út (ADC) tehát nem jobb, mint az eddig D-be vezető út. (ABC)
C szülője marad B.
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
12
5
1
5
E
∞
8 2
3
9
E: 5 + 1 = 6 < végtelen
8 G
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
12
5
1
5
E
6
8 2
3
9
Végtelen helyére 6.
8 G
D, mint E szülője megjegyezve
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
12
5
1
5
E
6
8 2
3
9
G: 5 + 2 = 7 < 8
8 G
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
12
5
1
5
E
6
8 2
3
7 G
9
Ez az út (ADG) tehát jobb, mint az eddig G-be vezető út. (AG)
G szülője ezentúl D.
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
12
5
1
5
E
6
8 2
3
9
Végeztünk D-vel.
7 G
(Nincs több szomszédja)
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
12
5
1
5
E
6
8 2
3
7 G
9
Válasszuk ki a legolcsóbban elérhető pontot a még nem szürkék közül. (E) Majd vizsgáljuk meg sorra a szomszédait.
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
12
5
1
5
E
6
8 2
3
9
F: 6 + 5 = 11 < 12
7 G
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
11
5
1
5
E
6
8 2
3
7 G
9
Ez az út (ADEF) tehát jobb, mint az eddig F-be vezető út. (ABF)
F szülője ezentúl E.
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
11
5
1
5
E
6
8 2
3
9
G: 6 + 3 = 9 > 7
7 G
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
11
5
1
5
E
6
8 2
3
7 G
9
Ez az út (ADEG) tehát nem jobb, mint az eddig G-be vezető út. (ADG)
G szülője marad D.
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
11
5
1
5
E
6
8 2
3
9
Végeztünk E-vel.
7 G
(Nincs több szomszédja)
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
11
5
1
5
E
6
8 2
3
7 G
9
Válasszuk ki a legolcsóbban elérhető pontot a még nem szürkék közül. (G) Majd vizsgáljuk meg sorra a szomszédait.
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
11
5
1
5
E
6
8 2
3
9
F: 7 + 9 = 16 > 11
7 G
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
11
5
1
5
E
6
8 2
3
7 G
9
Ez az út (ADGF) tehát nem jobb, mint az eddig F-be vezető út. (ADEF)
F szülője marad E.
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
11
5
1
5
E
6
8 2
3
9
Végeztünk G-vel.
7 G
(Nincs több szomszédja)
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
11
5
1
5
E
6
8 2
3
7 G
9
Válasszuk ki a legolcsóbban elérhető pontot a még nem szürkék közül. (C)
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
11
5
1
5
E
6
8 2
3
9
F: 9 + 1 = 10 < 11
7 G
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
10
5
1
5
E
6
8 2
3
7 G
9
Ez az út (ABCF) tehát jobb, mint az eddig F-be vezető út. (ADEF)
F szülője ezentúl C.
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
10
5
1
5
E
6
8 2
3
9
Végeztünk C-vel.
7 G
(Nincs több szomszédja)
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
10
5
1
5
E
6
8 2
3
7 G
9
Válasszuk ki a legolcsóbban elérhető pontot a még nem szürkék közül. (F) Nagyon nehéz feladat. Majd vizsgáljuk meg az összes szomszédját!
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
10
5
1
5
E
6
8 2
3
9
Végeztünk F-vel.
7 G
B
3
C
6
9
3 A 4
0
1 9
7 5
D
F
10
5
1
5
E
6
8 2
3
7 G
9
Így talán jobban látszik a végeredmény.
