Teorie grafů a her – Semestrální práce IDOS

Zadání

Uvažujte jednoduchý systém MHD s n zastávkami a jízdními řáady, které se každý den opakují. Jednotlivé spoje jsou dány počáteční stanicí, cílovou stanicí, časem odjezdu (v minutách od začátku dne) a dobou cesty v minutách. Navrhněte algoritmus a napište program, který pro zadaný čas, startovní a cílovou stanici nalezne nejrychlejší spojení. Předpokládejte, že žádné spoje ani dotazy na spojení nejdou přes půlnoc. Na prvním řádku vstupu je počet stanic n a počet spojů m. Na dalších m řádkcích je pro každý spoj startovní a cílová stanice, čas odjezdu a doba cesty. Na řádku m + 2 je počet testovacích dotazů N a na dalších N řádcích jsou data pro jednotlivé dotazy. Jeden dotaz se skládá ze tří čísel: číslo startovní stanice, číslo cílové stanice a čas (v minutách od začátku dne) od kdy se má spojení hledat. Na výstupu bude N řádků, pro každý dotaz jeden. Výsledek jednoho dotazu je posloupnost použitých spojů. Jeden spoj je dán dvojicí: (číslo stanice, čas odjezdu). vojice jsou uzavřeny v závorce a odděleny mezerou. Po použitých spojích následuje ještě jedna dvojice obsahující index cílové stanice a čas příjezdu do ní. Pokud pro daný dotaz spojení neexistuje, vypíše se prázdná závorka ’()’.

Příklad vstupu:

Očekávaný výstup:


Řešení

Zpráva (bez zadání)

Použitý algoritmus

Pro tuto úlohu jsem použil Dijkstrův algoritmus.

Dijkstrův algoritmus je nejrychlejší algoritmus pro nalezení nejkratší cesty ze zadaného vrcholu do ostatních vrcholů grafu.

Omezení Dijkstrova algoritmu

Dijkstrova algoritmu nefunguje na grafech které obsahují záporně ohodnocené hrany (záporné délky hran).

Toto omezení nám v této úloze nijak nevadí – úloha neobsahuje záporně ohodnocené hrany.

Složitost Dijkstrova algoritmu

Složitost Dijkstrova algoritmu závisí na implementaci prioritní fronty. V případe její implementace pomocí sekvenčního vyhledávání je složitost algoritmu O(|U|^{2}), při použití binární haldy O(|H|log_{2}|U|).

V našem případě se jedná o složitost O(|U|^{2})

Popis Dijkstrova algoritmu

Dijkstrův algoritmus prohledává graf do šířky to znamená že se vlna nešíří na základě počtu hran od zdroje, ale  vzdálenosti (váhy hran) od zdroje. Tato vlna se zpracovává jen pro uzly, k nimž již byla nejkratší cesta nalezena. Algoritmus si uchovává všechny uzly v prioritní frontě řazené dle vzdálenosti od zdroje – v první iteraci má pouze zdroj vzdálenost 0, všechny ostatní uzly jsou ve vzdálenosti nekonečno. Algoritmus v každém svém kroku vybere z fronty uzel s nejvyšší prioritou (nejnižší vzdálenost od již zpracované části grafu) a zařadí jej mezi zpracované potomky, přidá jej do fronty, nejsou-li tam již obsaženi, a ověří, zda nejsou blíže ke zdroji, než byli před zařazením právě vybraného uzlu mezi zpracované.

Pro všechny potomky se ověřuje:

Vzdalenost_{zpracovany} + DelkaHrany_{zpracovany.potomek} < Vzdalenost_{potomek}

Když nerovnost platí, tak danému potomkovi nastaví novou vzdálenost a označí za jeho předka zpracovaný uzel. Po průchodu přes všechny potomky algoritmus vybere z fronty uzel s nejvyšší prioritou a celý krok se opakuje.

Algoritmus se ukončí v okamžiku, kdy jsou zpracovány všechny uzly – to je když je prioritní fronta prázdná.

Ukázka Dijkstrova algoritmu na malém grafu
Ukázka Dijkstrova algoritmu

Ukázka Dijkstrova algoritmu

Pseudocode

Realizace

Pro vypracování semestrální práce jsem zvolil programovací jazyk C#. Algoritmem pro realizaci práce byl zvolen Dijkstrův algoritmus, který slouží pro nalezení nejkratší cesty v grafu. Pro reprezentaci zastávky byli použity vrcholy grafu. Spoje mezi zastávkami reprezentovali hrany grafu.


Program


Výsledek

Výsledek z testovacího serveru

Výsledek z testovacího serveru

Lukáš Vlček

Od roku 2011 jsem studentem informačních technologií na Technické Univerzitě v Liberci. Aktivně se zajímám o vývoj Windows a Android aplikací pod záštitou projektu Pillar Tech. V současné době jsem zaměstnán ve společnosti IBR Consulting s.r.o. kde modernizuji aplikaci pro řízení staveb – Aspe.