====== 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.

<note warning>
Při použití externích knihoven (např. ''heapq'', ''queue'' a podobně) bude práce hodnocena jako neodevzdaná (a to i zpětně)!
</note>


==== Zadání ====
Vytvořte soubor ''dijkstra.py'' a v něm vytvořte následující třídy:

<note tip>Můžete použít tuto šablonu: {{:courses:b6b36zal:zadani:dijkstra.py|}}</note>

=== 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í:

<code>
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)
</code>

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é:

<code>
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
</code>

V případě, že chceme znát nejkratší cesty do všech vrcholů z vrcholu Blueville tak řešení může vypadat následovně:\\

<code>
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
</code>

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}}

<note tip>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.</note>

==== 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.

<note warning>
Implementujte Dijkstrův algoritmus. Použití jiného algoritmu bude hodnoceno 0 body(a to i zpětně)!
</note>

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ů).

<note important>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.</note>


==== Bodování ====

<note>Ú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**
</note>