Cvičenie 9 – Cesty v grafoch

Ciele cvičení:

vedieť ako možno reprezentovať ohodnotený graf
vedieť zdôvodniť (dokázať) korektnosť a vedieť implementovať Bellman-Fordov algoritmus, Dijskstrov algoritmus a Floyd-Warshallov algoritmus

Ako to vlastne beží?

Ručne (na tabuli) alebo pomocou vizualizačného appletu odsimulujte výpočet Bellman-Fordovho a/alebo Dijsktrovho algoritmu.

Budujeme cesty

Bellman-Fordov a Dijsktrov algoritmus vypočítajú pre každý vrchol grafu dĺžku najkratšej cesty z vybraného štartovacieho vrcholu do daného vrcholu. Možno len z tejto informácie skonštruovať najkratšiu cestu (postupnosť vrcholov) zo štartovacieho vrcholu do ľubovoľného vrcholu grafu? Aká je efektívnosť tohto postupu?

Budujeme cesty – efektívne

Navrhnite spôsob, ako upraviť Bellman-Fordov a Dijsktrov algoritmus z prednášky tak, aby ste nielen vypočítali dĺžku najkratšej cesty, ale aj informáciu, pomocou ktorej je možné efektívne zrekonštruovať cestu (pre každý vrchol jeho predchodcu na najkratšej ceste)

Rada: sústreďte sa na operáciu relaxácie hrany
Vytvorte algoritmus, ktorý pomocou predvypočítaných predchodcov pre každý vrchol nájde cestu, ktorá do neho vedie zo štartovacieho vrcholu Bellman-Fordovho, resp. Dijkstrovho algoritmu.

Najkratšie cesty a grafy v matici

Reimplementujte algoritmy z prednášky (Bellman-Fordov, Dijkstrov a Floyd-Warshalov) tak, aby pracovali s grafom, ktorý je interne uložený v matici susednosti (ohodnoteného grafu). Ako budete uchovávať neprítomnosť hrany (ako to záleží od predpokladu ohodnotenia hrán)?

Najkratšie cesty v neorientovaných grafoch

Všetky algoritmy prezentované na prednáške fungujú len pre orientované grafy. Navrhnite, ako by trebalo upraviť tieto algoritmy (eventuálne bez úpravy vstupných grafov) tak, aby fungovali aj pre neorientované grafy.

Úpravu implementujte.

Budujeme cesty vďaka Floyd-Warshallovi

Navrhnite úpravu Floyd-Warshalovho algoritmu tak, aby ste pri požiadavke na „vypísanie“ najkratšej cesty medzi 2 vrcholmi vedeli túto cestu efektívne zrekonštruovať (2 možnosti, rozdiskutujte obe).

Dôkaz namiesto sľubov – Dijkstrov algoritmus

Rozdiskutujte dôkaz fungovania Dijkstrovho algoritmu (slidy, ktoré neboli na prednáške)

Nájdite graf obsahujúci hranu so zápornou cenou, na ktorom Dijsktrov algoritmus zlyhá (všimnite si, kde sa v Dijsktrovom algoritme využíva predpoklad nezápornosti cien na hranách).

Dijkstra vs. Bellman-Ford: rozhodnú to záporné hrany?

Bellman-Fordov algoritmus funguje narozdiel od Dijkstrovho algoritmu aj pre hrany so zápornými ohodnoteniami, avšak je pomalší. Nech graf obsahuje orientovanú hranu so záporným ohodnotením a nech X je najmenšie ohodnotenie hrany v takomto grafe (X < 0). Ak ku všetkým hranám grafu prirátame ohodnotenie |X|+1 (t.j. nové ohodnotenie hrany c(e) = c(e) + |X| + 1), všetky hrany grafu budú mať kladné ohodnotenie. Na takýto graf aplikujeme rýchlejší Dijkstrov algoritmus a získame najkratšie cesty v grafe (prirodzene na to, aby sme našli ohodnotenie cesty s k hranami, musíme od jej ohodnotenia odrátať hodnotu k*(|X|+1)). Je toto tvrdenie správne? Zdôvodnite, resp. nájdite kontrapríklad.

Funguje Bellman-Ford?

Ako sa správa Bellman-Fordov algoritmus, ak majú všetky hrany zápornú cenu? Je treba na takéto „zlé“ fungovanie mať všetky hrany záporné, alebo stačí orientovaný cyklus, ktorého súčet ohodnotení hrán je záporný?

Vysvetlenie: Všetky algoritmy prezentované ako algoritmy na nájdenie najkratších (najlacnejších) ciest v grafe sú v skutočnosti algoritmy na nájdenie najkratších (najlacnejších) sledov (walks) v grafe. Všimnime si napríklad, že ak v grafe nemáme záporné hrany, potom najkratší (najlacnejší) sled musí byť cesta. Dokonca platí, že ak graf neobsahuje cyklus záporný cyklus (cyklus so záporným súčtom cien jeho hrán), tak aj vtedy najkratší sled v grafe musí byť cestou. (Prečo?) Z toho dôvodu majú algoritmy predpoklad, že graf neobsahuje záporný cyklus – v opačnom prípade v grafe nemusí byť „najkratšia“ cesta.

A opäť bludisko

Uvažujme jednoduchú bludiskovú hru v 2-rozmernej mriežke – presne takú, ako bola v 3. prednáške. Avšak okrem „prekážkových“ políčok (stien) si pridajme do hracej plochy aj tzv. „spomaľovacie“ políčka. Spomaľovacie políčko spôsobí, že vždy, keď na neho vstúpime, „panáčik“ musí na tomto políčku ostať stáť („je zmrazený“) zadaný počet sekúnd. Pre každé spomaľovacie políčko môže byť definovaný iný čas, koľko tam musíme ostať stáť. Vytvorte program, ktorý pre zadanú štartovaciu pozíciu „panáčika“ a pozíciu východu z bludiska nájde najrýchlejšiu cestu z bludiska.