4.5.2. A Warshall-módszer

iDevice ikon

A módszer az összes pontból az összes pontba vezető legrövidebb utat adja meg.

A gráf éleinek hosszát egy táv nevű szomszédsági mátrixban tartjuk; a közvetlen szomszédok közti távolságok kiinduláskor adottak, a többi távolság pedig legyen végtelen. (Illetve választhatunk az élek össz-hosszánál, itt egy 350-nél nagyobb számot.)

Lépések sorozatával el akarjuk érni, hogy az összes távolság helyébe a két pont közti egyre rövidebb út hossza kerüljön. Ahhoz, hogy a nem szomszédos pontok közti távolságról beszélhessünk, egyértelműen meg kell határozni annak útját (tehát a csatlakozó élek sorozatát), azaz legalább azt kell ismernünk, hogy melyik ponton keresztül kell oda elindulni.

Egy másik, merre nevű mátrixban fogjuk jegyezni, hogy az egyik pontból melyik pont felé kell elindulni, hogy a másikba jussunk. Ezek a pontértékek a nem szomszédos pontok viszonylatában kiinduláskor még ismeretlenek.

Lépésenként az összes W pontra végignézünk minden X-Y viszonylatot, hogy annak pillanatnyi távolsága a W ponton át lerövidíthető-e. Tehát ha az X-Y aktuális távolság csökkenthető a W-n keresztül (távXY >távXW+távWY), akkor a távXY-t felülírjuk a két távolság összegével, és a merreXY-ba bejegyezzük a W pontot, amin keresztül pillanatnyilag a legrövidebb út vezet X-ből Y-ba.

A példa 8 pontjának mindegyikére 8x8 viszonylatot ellenőrzünk le, és két helyen javítunk, ha rövidebbet találunk az addigi távolságnál.

Kiindulási mátrixok (konkrét számítógépes megvalósításnál a végtelent helyettesítse pl. 500):

táv

A

B

C

D

E

F

G

H


merre

A

B

C

D

E

F

G

H

A

0

30

∞

∞

40

∞

∞ ∞


A

A

B



E




B

30

0

10

∞

∞ ∞

20

∞


B

A

B

C




G


C

∞

10

0

30

∞

20

∞

∞


C


B

C

D


F



D

∞

∞

30

0

∞

∞

∞

50


D



C

D




H

E

∞

20

∞

∞

0

10

∞

∞


E


B



E

F



F

∞

∞

∞

50

∞

0

∞

∞


F




D


F



G

40

∞

∞

∞

∞

∞

0

10


G

A






G

H

H

∞

∞

20

∞

∞

∞

10

0


H



C




G

H

Az 1. lépésben megpróbálkozunk az A pont bevonásával; eldöntjük az összes X-ből Y pontba tartó útvonal távolságáról, hogy rövidebb lenne-e, amikor az X-ből az A-ba, majd az A-ból az Y-ba tartunk. (Az aktuális lépésben történt javítások színe: kék.)

Pl. távGB helyébe kerül a távGA+távAB=40+30, ami ugyebár kisebb a végtelennél.

táv

A

B

C

D

E

F

G

H


merre

A

B

C

D

E

F

G

H

A

0

30

∞

∞

40

∞

∞

∞


A

A

B



E




B

30

0

10

∞

70

∞

20

∞


B

A

B

C


A


G


C

µ

10

0

30

∞

20

∞

∞


C


B

C

D


F



D

∞

∞

30

0

∞

∞

∞

50


D



C

D




H

E

∞

20

∞

∞

0

10

∞

∞


E


B



E

F



F

∞

∞

∞

50

∞

0

∞

∞


F




D


F



G

40

70

∞

∞

80

∞

0

10


G

A

A



A


G

H

H

∞

∞

20

∞

∞

∞

10

0


H



C




G

H

2. lépésben a B pont bevitelével próbálkozunk utakat rövidíteni:

táv

A

B

C

D

E

F

G

H


merre

A

B

C

D

E

F

G

H

A

0

30

40

∞

40

∞

50

∞


A

A

B

B


E


B


B

30

0

10

∞

70

∞

20

∞


B

A

B

C


A


G


C

40

10

0

30

80

20

30

∞


C

B

B

C

D

B

F

B


D

∞

∞

30

0

∞

∞

∞

50


D



C

D




H

E

50

20

30

∞

0

10

40

∞


E

B

B

B


E

F

B


F

∞

∞

∞

50

∞

0

∞

∞


F




D


F



G

40

70

80

∞

80

∞

0

10


G

A

A

B


A


G

H

H

∞

∞

20

∞

∞

∞

10

0


H



C




G

H

A C pont bevonása alkalmával újabb 17 viszonylatban rövidítünk:

táv

A

B

C

D

E

F

G

H


merre

A

B

C

D

E

F

G

H

A

0

30

40

70

40

60

50

∞


A

A

B

B

C

E

C

B


B

30

0

10

40

70

30

20

∞


B

A

B

C

C

A

C

G


C

40

10

0

30

80

20

30

∞


C

B

B

C

D

B

F

B


D

70

40

30

0

110

50

60

50


D

C

C

C

D

C

C

C

H

E

50

20

30

60

0

10

40

∞


E

B

B

B

C

E

F

B


F

∞

∞

∞

50

∞

0

∞

∞


F




D


F



G

40

70

80

110

80

100

0

10


G

A

A

B

C

A

C

G

H

H

60

30

20

60

100

40

10

0


H

C

C

C

C

C

C

G

H

D bevonása alkalmával már nem csak a végtelennel kell összehasonlítanunk - pl. távCA
a D-n át nem lesz rövidebb (40<30+70):

táv

A

B

C

D

E

F

G

H


merre

A

B

C

D

E

F

G

H

A

0

30

40

70

40

60

50

120


A

A

B

B

C

E

C

B

D

B

30

0

10

40

70

30

20

90


B

A

B

C

C

A

C

G

D

C

40

10

0

30

80

20

30

80


C

B

B

C

D

B

F

B

D

D

70

40

30

0

110

50

60

50


D

C

C

C

D

C

C

C

H

E

50

20

30

60

0

10

40

110


E

B

B

B

C

E

F

B

D

F

120

90

80

50

160

0

110

100


F

D

D

D

D

D

F

D

D

G

40

70

80

110

80

100

0

10


G

A

A

B

C

A

C

G

H

H

60

30

20

50

100

40

10

0


H

C

C

C

C

C

C

G

H

Az E, F, G, H bevitele során többször is javítjuk a távolságokat és velük együtt a köztes pontokat.

táv

A

B

C

D

E

F

G

H


merre

A

B

C

D

E

F

G

H

A

0

30

40

70

40

50

50

120


A

A

B

B

C

E

E

B

D

B

30

0

10

40

70

30

20

90


B

A

B

C

C

A

C

G

D

C

40

10

0

30

80

20

30

80


C

B

B

C

D

B

F

B

D

D

70

40

30

0

110

50

60

50


D

C

C

C

D

C

C

C

H

E

50

20

30

60

0

10

40

110


E

B

B

B

C

E

F

B

D

F

120

90

80

50

160

0

110

100


F

D

D

D

D

D

F

D

D

G

40

70

80

110

80

90

0

10


G

A

A

B

C

A

E

G

H

H

60

30

20

50

100

40

10

0


H

C

C

C

C

C

C

G

H

Az F bevonása ugyan semmin sem javít, de a G hat esetben is rövidít:

táv

A

B

C

D

E

F

G

H


merre

A

B

C

D

E

F

G

H

A

0

30

40

70

40

50

50

60


A

A

B

B

C

E

E

B

G

B

30

0

10

40

70

30

20

30


B

A

B

C

C

A

C

G

G

C

40

10

0

30

80

20

30

40


C

B

B

C

D

B

F

B

G

D

70

40

30

0

110

50

60

50


D

C

C

C

D

C

C

C

H

E

50

20

30

60

0

10

40

50


E

B

B

B

C

E

F

B

G

F

120

90

80

50

160

0

110

100


F

D

D

D

D

D

F

D

D

G

40

70

80

110

80

90

0

10


G

A

A

B

C

A

E

G

H

H

50

30

20

50

90

40

10

0


H

G

C

C

C

G

C

G

H

Végül a H bevonásával 4 viszonylatban is rövidíthetünk (a G-F viszonylatot megint):

táv

A

B

C

D

E

F

G

H


merre

A

B

C

D

E

F

G

H

A

0

30

40

70

40

50

50

60


A

A

B

B

C

E

E

B

G

B

30

0

10

40

70

30

20

30


B

A

B

C

C

A

C

G

G

C

40

10

0

30

80

20

30

40


C

B

B

C

D

B

F

B

G

D

70

40

30

0

110

50

60

50


D

C

C

C

D

C

C

C

H

E

50

20

30

60

0

10

40

50


E

B

B

B

C

E

F

B

G

F

120

90

80

50

160

0

110

100


F

D

D

D

D

D

F

D

D

G

40

40

30

60

80

50

0

10


G

A

H

H

H

A

H

G

H

H

50

30

20

50

90

40

10

0


H

G

C

C

C

G

C

G

H

Az egyes távolságok az összes bevonható pontnak köszönhetően biztosan a lehető legrövidebb távolságok a táv-ban. A köztes pontok tisztázása az egyes viszonylatokban még hátravan, ui. több köztes pont esetén nem feltétlenül az első köztes pontot tartalmazza a MERRE mátrix.

Figyeljük meg a viszonylatokat a köztes pontok szempontjából:

  • a merreXY=Y, amikor nincs köztes pont az X-Y viszonylatban.
  • merreXY=Z és merreXZ=Z, akkor egy köztes pont van: Z.
  • egyébként több köztes pont esetén visszafelé haladva ki kell olvasni az első köztes pontot az X-Y viszonylatban, azaz azt a pontot, amely felé az X pontból el kell indulni.

Összesen öt olyan eset van, amikor adott viszonylatban a kezdőpontból nem egy szomszédos pont felé javasolt az elindulás:

  • merreAD=C és merreAC=B és merreAB=B, tehát merreAD javított értéke: B
  • a merreED javított értéke szintén B
  • hasonlóan a merreAH, merreCH és merreEH sem lehet G, mert az nem szomszédja sem az A-nak, sem a C-nek, sem az E-nek, de visszafelé haladva az úton itt is a B-hez jutunk.

Ezeket az eseteket - a javításokat - pirossal átvezetjük a merre mátrixban:

 

merre

A

B

C

D

E

F

G

H

A

A

B

B

B

E

E

B

B

B

A

B

C

C

A

C

G

G

C

B

B

C

D

B

F

B

B

D

C

C

C

D

C

C

C

H

E

B

B

B

B

E

F

B

B

F

D

D

D

D

D

F

D

D

G

A

H

H

H

A

H

G

H

H

G

C

C

C

G

C

G

H

 

Az alapfeladatra válaszolva: bármelyik kezdőpontból az összes többibe tartó minimális út hosszát kiolvashatjuk a táv mátrixból, az útvonal által érintett köztes pontokat pedig a merre mátrixból.

táv

A

B

C

D

E

F

G

H


merre

A

B

C

D

E

F

G

H

A

0

30

40

70

40

50

50

60


A

A

B

B

B

E

E

B

B

B

30

0

10

40

70

30

20

30


B

A

B

C

C

A

C

G

G

C

40

10

0

30

80

20

30

40


C

B

B

C

D

B

F

B

B

D

70

40

30

0

110

50

60

50


D

C

C

C

D

C

C

C

H

E

50

20

30

60

0

10

40

50


E

B

B

B

B

E

F

B

B

F

120

90

80

50

160

0

110

100


F

D

D

D

D

D

F

D

D

G

40

40

30

60

80

50

0

10


G

A

H

H

H

A

H

G

H

H

50

30

20

50

90

40

10

0


H

G

C

C

C

G

C

G

H


iDevice ikon

Olvassunk ki néhány legrövidebb utat!

  • A D-H út egyetlen, 50 hosszú útszakaszból áll.
  • Az A-G távolság 50, és B-n keresztül vezet.
  • Az F-B 3 útszakaszból 90 hosszúságú: F-D-C-B.
  • Az F-ből a G-be a D-C-B érintésével lehet az optimális, 110-es távolságot megtenni.

Megjegyzés: az egyenlőségek esetében történő választás miatt több optimális megoldás is előfordulhat.


« Előző | Következő »