====== 10. úkol - Dijkstra ======
Vaším desátým úkolem je naimplementovat [[https://cs.wikipedia.org/wiki/Dijkstr%C5%AFv_algoritmus|Dijkstrův algoritmus]] a použít ho k hledání nejkratších cest v grafu ([[https://en.wikipedia.org/wiki/Shortest_path_problem|Shortest Path Problem]]). Graf dostanete zadán pomocí struktur (vrcholy a hrany) s tím, že hrany jsou kladně ohodnoceny a jsou orientované. V grafu mohou být cykly.
Při použití externích knihoven (např. ''heapq'', ''queue'' a podobně) bude práce hodnocena jako neodevzdaná (a to i zpětně)!
==== Zadání ====
Vytvořte soubor ''dijkstra.py'' a v něm vytvořte následující třídy:
Můžete použít tuto šablonu: {{:courses:b6b36zal:zadani:dijkstra.py|}}
=== Edge ===
Třída reprezentující hranu v grafu. Tato třída má následující atributy:
* ''source'' - numerický identifikátor vrcholu, v kterém hrana začíná (celočíselný typ)
* ''target'' - numerický identifikátor vrcholu, v kterém hrana končí (celočíselný typ)
* ''weight'' - váha hrany (celočíselný typ)
Třída musí mít metodu ''%%__init__(self, source, target, weight)%%'' která je zavolána při vytvoření třídy a příjímá ID zdrojového vrcholu (''source''), ID cílového vrcholu (''target'') a váhu hrany (''weight''). Nastavení ostatních parametrů (pokud je potřebujete) je již ve vaší režii. Můžete jejich nastavení přidat do metody ''%%__init__()%%'', nebo můžete využít metodu pro inicializaci grafu ''createGraph()''.
\\
=== Vertex ===
Třída reprezentující vrchol v grafu. Tato třída má následující atributy:
* ''id'' - numerický identifikátor vrcholu (celočíselný typ)
* ''name'' - jméno vrcholu (znakový řetězec)
* ''edges'' - hrany, které začínají v tomto vrcholu (seznam typu Edge)
* ''minDistance'' - minimální vzdálenost, za kterou se lze dostat do tohoto vrcholu z vrcholu, nad kterým byla provedena funkce ''computePath()'' (celočíselný typ)
* ''previousVertex'' - předchozí vrchol - vrchol, přes který vede cesta do tohoto vrcholu pro minimální cestu (typ Vertex)
Třída musí mít metodu ''%%__init__(self, id, name)%%'', tj. konstruktor, jež nastavuje vrcholu jeho id (''id'') a název (''name''). Nastavení ostatních parametrů (pokud je potřebujete) je ve vaší režii.
\\
=== Dijkstra ===
Třída reprezentující Dijkstrův algoritmus. Tato třída má pouze jednu proměnnou
* ''vertexes'' - vrcholy grafu, nad kterými chceme provádět Dijkstrův algoritmus
Třída má tyto metody:
* ''createGraph(self, vertexes, edgesToVertexes)'' - vytvoří graf ze zadaných vrcholů. ''Vertexes'' je seznam objektů typu ''Vertex'' a ''edgesToVertexes'' je seznam objektů typu ''Edge''.
* ''getVertexes(self)'' - metoda vrátí vrcholy, nad kterými je možné provést Dijkstrův algoritmus.
* ''computePath(self, sourceId)'' - metoda nalezne nejkratší cesty z vrcholu se ''sourceId'' do všech vrcholů v grafu. Metoda nic nevrací, ale po skončení operace by měly mít všechny vrcholy vyplněnou proměnou ''minDistance'', která reprezentuje minimální vzdálenost do daného vrcholu.
* ''getShortestPathTo(self, targetId)'' - metoda vrátí list vrcholů, přes které vede z vrcholu ''sourceId'' - nad kterými byla spuštěna operace ''computePath()'' - do vrcholu specifikovaného v ''targetId''.
* ''resetDijkstra(self)'' - tato metoda vynuluje aktuální výsledky po průchodu Dijkstrovým algoritmem. Metoda nerozpojí či nezahodí graf, pouze ho vrátí do stavu, v jakém byl před operací ''computePath()''
Proměnné ''sourceId'' a ''targetId'' jsou číselné. Je nutné si tedy zadaný graf uložit a poté vrcholy najít na základě jejich ID.
Dijkstrův algoritmus počítá s tím, že vzdálenost vrcholů, které nezpracoval je nekonečno. V Pythonu ho prosím reprezentujte takto: ''float('inf')''
==== Příklad použití a ukázka ====
Vzhledem k delšímu zápisu příkladu použtí je příklad umístěn v souboru {{courses:b6b36zal:zadani:dijkstrause.py|dijkstrause.py}}.
Níže je graf, který by vám měl vzniknout po správné konstrukci přiloženého příkladu:
{{courses:b6b36zal:zadani:10-graph.png?400|test.png}}
Operace computePath nad vrcholem Redville našla v grafu nejkratší cesty a proto jsou minimální vzdálenosti z tohoto vrcholu následující:
Printing min distance from vertex:Redville
Min distance to:Redville is: 0 - #V Redville začínáme
Min distance to:Blueville is: 5 - # Do Blueville se dostaneme přímou cestou hranou s vahou 5
Min distance to:Greenville is: 8 - # Do Greenville se se dostaneme nejlevněji přes Blueville (5) a poté do Greenville (3)
Min distance to:Orangeville is: 8 - # Do Orangeville se dostaneme nejlevněji přímou cestou hranou s vahou 8
Min distance to:Purpleville is: 10 - # Do Purpleville se dostaneme nejlevněji přes Orangeville (8) a poté do Greenville (2)
Poté resetujeme nastavení Dijkstry a necháme ji spočítat to samé pro další vrchol s ID 1 (Blueville) - doplnění cest je zřejmé:
Printing min distance from vertex:Blueville
Min distance to:Redville is: 5
Min distance to:Blueville is: 0
Min distance to:Greenville is: 3
Min distance to:Orangeville is: 9
Min distance to:Purpleville is: 7
V případě, že chceme znát nejkratší cesty do všech vrcholů z vrcholu Blueville tak řešení může vypadat následovně:\\
Printing min distance from vertex:Blueville
Min distance to:Redville is: 5
Path is: Blueville, Redville
Min distance to:Blueville is: 0
Path is: Blueville
Min distance to:Greenville is: 3
Path is: Blueville, Greenville
Min distance to:Orangeville is: 9
Path is: Blueville, Purpleville, Orangeville
Min distance to:Purpleville is: 7
Path is: Blueville, Purpleville
Výše uvedené výpisi jsou výpisy ze souboru, kde je naznačeno jak si vaší implementaci můžete testovat.{{courses:b6b36zal:zadani:dijkstrause.py|dijkstrause.py}}
Dijkstrův algoritmus používá k ukládání vrcholů, které jsou nejblíže k zdrojovému vrcholu prioritní frontu. Použijte ji také - nepoužití prioritní fronty může znamenenat, že se vaše SPT budou lišit. Pokud přidáváte do prioritní fronty vrchol, jehož minimální cena se shoduje s některým vrcholem, který již ve frontě je, pak ho vložte před tento vrchol.
==== Testování ====
Náš skript bude testování provádět obdobně jako je tomu v referenčním případě s tím rozdílem, že z vaší strany není nutné cokoliv vypisovat. Testovací skript si vytvoří instanci ''Dijkstra()'' a bude nad ní postupně volat metody, které chce otestovat. Poté si vždy pomocí metody ''getVertexes()'' získá aktuální reprezentaci grafu a tu porovná s referenčním řešením.
Implementujte Dijkstrův algoritmus. Použití jiného algoritmu bude hodnoceno 0 body(a to i zpětně)!
Testování je rozděleno do několika bodů. V případě 3. bodu jsou vám zadávány náhodně generované grafy. U těchto grafů se může stát, že nebudou spojté. V případě nespojtého grafu provádíte operace pouze nad částmi, které jsou spojté. Nejkratší cestu do nedostupného vrcholu reprezentuje **prázdný seznam** (vrcholů).
Kromě správnosti řešení testujeme také jeho výkon. Hranice jsou nastaveny dostatečně vysoko, ale v případě, že vaše řešení neprochází na čas, spojte se s cvičícím.
==== Bodování ====
Úloha je hodnocena max. **8 body**, které jsou udělovány následovně:
- Funguje vám správně část Dijkstry, která počítá minimální vzdálenosti na základních datech: **2 body**
- Funguje vám správně část Dijkstry, která počítá minimální vzdálenosti a nejkratší cestu základních datech: **2 body**
- Funguje vám správně část Dijkstry, která počítá minimální vzdálenosti a cesty na náhodných grafech: **4 body**