4.5.3. A Dijkstra-módszer

A módszer egy adott kezdőpontból az összes többi pontba vezető minimális utakat adja meg, vagyis egy faépítésről van szó, mely a gráf minden pontját tartalmazza a kezdőpontból - mint gyökérből induló - legrövidebb úttal.

A fa éleiről tudjuk, hogy minden utódból egyértelműen „mutatnak" a szülőre, és irányítatlan esetben bárhonnan bármely pontba úton eljuthatunk.

A kiindulásnál kizárólag az adott pont része a fának, mégpedig az a gyökere, mert annak nincs szülője. A faépítés során az egyes pontok lépésenként kerülnek be a fába, de amint egy pont bekerül, annak utódai máris aktív pontokká válnak, mert onnantól kiszámolható távolságra lesznek a gyökértől.

Példa-hálózatunkban legyen most az adott pont az A.

A kiindulási pont lesz a fa gyökere*, ezért az máris része a fának (bent van). A fába került pont lehetséges közvetlen utódainál a szülőt bejelöljük és kiszámítjuk a gyökértől lévő távolságot, mint a szülő távolságának és a szülő-utód él súlyának az összegét (jelen esetben az ábráról olvassuk le a súlyokat). Ezzel a pont vagy most lett aktív, vagy már aktív is volt, de csak a rövidebb távolság esetén írjuk felül a régi szülőt és távolságot. Azonos távolság esetén tetszőlegesen választhatunk, tehát több optimális fát is építhetünk.

Láthatóan csak az A van a fában (színezzük sötétre), az utódai: B és E aktív pontok lettek (színezzük szürkére):

*pontok*	A	B	C	D	E	F	G	H
szülő	*	A			A
táv	0	30			40
bent van	+	-			-

Az aktív pontok közül mindig az a pont kerüljön a fára, melynek a távolsága a gyökértől a lehető legkisebb. Mivel 30<40 most a B „érett meg arra, hogy bekerüljön a fába". Folytatjuk B lehetséges utódaival (C, G), majd az aktív pontok közül választunk újabb végleges pontot a fához (vagy C, vagy E).

*pontok*	A	B	C	D	E	F	G	H
szülő	*	A	B		A		B
táv	0	30	30+10		40		30+20
bent van	+	+	-		-		-

C választásával D és F lesz aktív, mert azok a C lehetséges utódai (a B már nem lehet utód):

*pontok*	A	B	C	D	E	F	G	H
szülő	*	A	B	C	A	C	B
táv	0	30	40	70	40	60	50
bent van	+	+	+	-	-	-	-

Az aktív pontok távolságának minimuma: 40. A bekerülő pont az E, mely lehetséges utódja csak az F, javításra kerül:

*pontok*	A	B	C	D	E	F	G	H
szülő	*	A	B	C	A	E	B
táv	0	30	40	70	40	50	50
bent van	+	+	+	-	+	-	-

A következő fába épülő pont legyen az F (50-nel), amely a D szülőjeként nem javítaná a D gyökértől való távolságát.

*pontok*	A	B	C	D	E	F	G	H
szülő	*	A	B	C	A	E	B
táv	0	30	40	70	40	50	50
bent van	+	+	+	-	+	+	-

Következik a G, lehetséges utódja a H:

*pontok*	A	B	C	D	E	F	G	H
szülő	*	A	B	C	A	E	B	G
táv	0	30	40	70	40	50	50	60
bent van	+	+	+		+	+	+	-

A H van legközelebb a gyökérhez az aktív pontok közül, de utód nélkül marad:

*pontok*	A	B	C	D	E	F	G	H
szülő	*	A	B	C	A	E	B	G
táv	0	30	40	70	40	50	50	60
bent van	+	+	+		+	+	+	+

Végül a D kerül be a fába:

*pontok*	A	B	C	D	E	F	G	H
szülő	*	A	B	C	A	E	B	G
táv	0	30	40	70	40	50	50	60
bent van	+	+	+	+	+	+	+	+

Jelöljük be a fa éleit a hálózatban: látjuk, hogy egy minden pontot érintő részgráfot kapunk, melyben minden pontnak a gyökértől lévő távolsága minimális.

Valójában a fában nem szereplő élek törlésével világosabb ábrát kapunk; de a leginkább szemlétes a standard elhelyezés, amikor a gyökér van fent, és az utódok szintenként lefelé helyezkednek el a szülőtől:

Alkossuk meg ugyanezzel az algoritmussal a B pontból* épített minimális fát!

*pontok*	A	B	C	D	E	F	G	H
szülő	B	*	B				B
táv	30	0	10				20
bent van	-	+	-				-

*pontok*	A	B	C	D	E	F	G	H
szülő	B	*	B	C		C	B
táv	30	0	10	40		30	20
bent van	-	+	+	-		-	-

*pontok*	A	B	C	D	E	F	G	H
szülő	B	*	B	C		C	B	G
táv	30	0	10	40		30	20	30
bent van	-	+	+	-		-	+	-

*pontok*	A	B	C	D	E	F	G	H
szülő	B	*	B	C	A	C	B	G
táv	30	0	10	40	70	30	20	30
bent van	+	+	+	-	-	-	+	-

*pontok*	A	B	C	D	E	F	G	H
szülő	B	*	B	C	A	C	B	G
táv	30	0	10	40	70	30	20	30
bent van	+	+	+	-	-	+	+	+

*pontok*	A	B	C	D	E	F	G	H
szülő	B	*	B	C	A	C	B	G
táv	30	0	10	40	70	30	20	30
bent van	+	+	+	+	+	+	+	+

A B-ből induló minimális fa:

Megjegyzések:

A 2 minimális fát összevetve a Warshall-mátrixbeli eredményekkel, nem találunk különbséget.
A 2 minimális fa összehasonlítható az útvonalak hosszainak összege alapján, és megállapíthatjuk, hogy a B-ből eredő minimális fa (230) kedvezőbb az A gyökerűnél (340). Erre támaszkodik a Prim-algoritmus a minimális feszítőfa építésénél.

Végezetül illik felírnunk a példa-hálózat él-vektoros tárolási módját, mert az imént az ábráról egyszerűen „lepuskáztuk" a bevitt pontok szomszédjait és a súlyokat!

pontok:	A	B	C	D	E	F	G	H
a pontból induló 1. él mutatója:	1.	3.	6.	9.	11.	13.	14.	16.

élek:	1.	2.	3.	4.	5.	6.	7.	8.	9.	10.	11.	12.	13.	14.	15.	16.	17.
végpont	B	E	A	C	G	B	D	F	C	H	B	F	D	A	H	C	G
távolság	30	40	30	10	20	10	30	20	30	50	20	10	50	40	10	20	10

Gyakorlatok

Érdekességképpen ugyanezt a két feladatot megoldva irányítatlan esetben (valójában 'a minden él kétirányú' esetre), arra jutunk, hogy az összes útvonal teljes hossza még kedvezőbb a B-ből induló minimális fa kiépítésénél az A-gyökerű minimális fához képest.

Legyen az alábbi hálózat minden éle kétirányú, azaz minden élen bármely irányban haladhat az út.

Az A kezdőpontból épített minimális fa előállítása:

A két 50-es pont (F, H), végül a 70-es D pont bevitele már nem javított semmit:

*pontok*	A	B	C	D	E	F	G	H
szülő	*	A	B	C	A	E	A	G
táv	0	30	40	70	40	50	40	50
bent van	+	+	+	+	+	+	+	+

Az A-ból induló minimális fában az összes többi pontba vezető útvonalak teljes hossza 320.

Az A-gyökerű minimális fa ábrája teljesen szemléletes:

A B kezdőpontból épített minimális fa előállítása:

Végül a 40-es utolsó ponttal készült el a fa:

*pontok*	A	B	C	D	E	F	G	H
szülő	B	*	B	C	B	C	B	C
táv	30	0	10	40	20	30	20	30
bent van	+	+	+	+	+	+	+	+

A B-ből induló minimális fában az összes többi pontba vezető útvonalak teljes hossza 180.

A B-gyökerű minimális fa ábrája szemléletesebben:

« Előző | Következő »