Zázvorové pivo

Závozník Zachariáš sa živí rozvozom zázvorového piva. Pivo je síce nezdravé, ale všetkým pupkatým zbrojnošom preveľmi chutí, takže Zachariáš pekne zarába a dňom i nocou bohatne. Má to iba jeden háčik. Vždy, keď náš Zachariáš vstúpi s vozom piva do hocijakého mesta, musí zaplatiť mýto a to sa mu veru vôbec, ale vôbec nepáči. Teraz práve je v meste A a chcel by sa dostať do mesta B, kde sa má konať veľký jarmok, na ktorom sa jeho pivo určite bude dobre predávať. Chce tam však docestovať tak, aby musel cestou platiť mýto v čo najmenej mestách. A tak sedí zadumaný na voze a premýšľa.

Úloha:
Na vstupe máte zadané prirodzené číslo n > 1 určujúce počet miest (mestá sú číslované číslami 1 až n), číslo m určujúce počet ciest a ďalej zoznam týchto ciest. Každá cesta vedie medzi dvoma mestami a je zadaná dvojicou čísel týchto miest. Ďalej sú zadané čísla miest A a B. Zistite, či sa Zachariáš môže dostať z mesta A do mesta B. Ak áno, vypíšte trasu, vedúcu z A do B cez najmenší možný počet miest. Ak je takýchto trás viac, vypíšte ľubovoľnú.

Príklad:

n=7, m=6 cesty: 1 6 2 3 2 7 4 7 4 5 3 5 A=3, B=4

Výsledkom je trasa idúca cez mestá 3,5 a 4. Existuje ešte trasa 3, 2, 7, 4 tá však ide cez viacej miest. Ak by sa však Zachariáš chcel dostať z mesta A=3 do mesta B=1, odpoveďou programu by malo byť, že cesta neexistuje.

.

Dijkstrov algoritmus.

Vstup: Graf G = (V, E), ohodnotenie hrán w(e), e Î E, štartovný vrchol s Î V.
Premenné: čísla d(v), v Î V , číslo d, množiny A, N . V.
Výstup: Po skončení algoritmu udáva d(v) cenu najlacnejšej cesty do v z s, pre každé v Î V .

• Krok 1: (Inicializácia)
  
  d(s) := 0, d(v) := Ą pre v Î V \ { s } ; A := V .
  
• Krok 2: (Test ukončenia)
  
  Ak pre všetky v Î A platí d(v) = Ą, algoritmus končí, inak sa pokračuje krokom 3.
  
• Krok 3: (Voľba množiny N)
  
  d := min { d(y); y Î A } , N := { v Î A; d(v) = d } , A := A \ N
  
• Krok 4: (Aktualizácia d(y) pre všetkých susedov N)
  
  Pre každú hranu e = { v, y } , kde v Î N a y Î A, preveď príkaz
  
     d(y) := min { d(y), d(v) + w(e) } .
  
  Po vyčerpaní všetkých takých hrán e pokračuj krokom 2.

Dôkaz správnosti algoritmu.
Zrejme cyklus prebehne toľkokrát, koľko rôznych konečných cien z vrchola s do ostatných vrcholov v grafe G existuje (predpokladajme k). Stačí si uvedomiť, že po i-tom prechode cyklu (1 <= i <= k) v každom vrchole v Î V hodnota d(v) udáva najmenšiu možnú cenu z ciest obsahujúcich nanajvýš i hrán z vrchola s do vrchola v.

Poznámka. Predchádzajúci algoritmus spracuje graf o n vrcholoch v čase O(n ² ).

Pri riešení použijeme modifikovaný Dijkstrov algoritmus. Dijkstrov algoritmus nám totiž umožňuje nájsť cenu najlacnejšej cesty medzi dvoma vrcholmi s,v číslo d(v) ale mi potrebujeme navyše aj vypísať túto cestu. Preto si budeme poradie vrcholov v ceste zvlášť pamätať.

.

Zdroje

• Dijkstra's and other Algorithms