Semestrální práce z předmětu Teoretická informatika
Jiří Mlejnek
cvičení: Čtvrtek 11:00
Zadání:
Nechť je pro orientovaný graf G=(H,U) s ohodnocením hran w známo, že obsahuje cyklus se zápornou w-délkou. Navrhněte efektivní algoritmus, který určí všechny uzly ležící na nějakém takovém cyklu.
Řešení:
Pro hledání uzlů ležících na záporném cyklu jsem použil algoritmus Floyd-Warshall, který počítá nejkratší vzdálenosti mezi všemi páry uzlů ze zadané w-matice. Pokud algorimtnus najde cestu se zápornou délkou se shodným počátečním a koncovým bodem ( prvky na diagonále mají hodnotu menší než nula ) musí tento uzel ležet na záporném cyklu.
Vstupem do programu je název souboru obsahující w-matici, předávaný pomocí příkazové řádky. První prvek matice odpovídá uzlu s číslem 1. Neexistuje-li hrana mezi danou dvojicí uzlů stačí použít ohodnocení řádově mnohem větší než ohodnocení ostatních hran. Já jsem použil ohodnocení w=1000. Pro vyzkoušení programu jsem připravil dva soubory graf1.txt a graf2.txt,které obsahují grafy, jejichž grafická podoba je nakreslena níže.
Grafická podoba grafu ze souboru graf1.txt:
Grafická podoba grafu ze souboru graf2.txt:
