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


==== Zadání ====
Vytvořte soubor dijkstra.py (můžete využít šablonu {{:courses:b6b36zal:zadani: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í proměnné:
  * source - numerický identifikátor vrcholu, v kterém hrana začíná (int)
  * target- numerický identifikátor vrcholu, v kterém hrana končí (int)
  * weight - váha hrany (int)

Třída musí mít metodu:
<code>__init__(self,source,target,weight)</code>
 - 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). Skript při vytváření hran použije pouze metodu init tzn skript nastaví source, target a weight. Nastavení ostatních parametrů (pokud je potřebujete) je již ve vaší režii. Můžete jejich nastavení samozřejmě přidat do metody init na tomto objektu, nebo můžete využít inicializace grafu v Dijkstře (createGraph).

=== Vertex ===
Třída reprezentující vrchol v grafu. Tato třída má následující proměnné:
  * id - numerický identifikátor vrcholu (int)
  * name - jméno vrcholu (String)
  * minDistance - minimální vzdáletost, za kterou se lze dostat do tohoto vrcholu (int) z vrcholu, nad kterým byla provedena funkce computePath. 
  * previousVertex - předchozí vrchol - vrchol, přes který vede cesta do tohoto vrcholu pro minimální cestu (Vertex)
  * edges - hrany, které začínají v tomto vrcholu (list of Edge)

Třída musí mít metodu <code>__init__(self,id,name)</code>, která se volá při vytvoření a natavuje vrcholu jeho id (id) a název(name). Skript při vytváření vrcholů použije pouze metodu init tzn skript nastaví id a jméno. Nastavení ostatních parametrů (pokud je potřebujete) je již ve vaší režii. Můžete jejich nastavení samozřejmě přidat do metody init na tomto objektu, nebo můžete využít inicializace grafu v Dijkstře (createGraph).

=== Dijkstra ===
Třída reprzentují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 operace:

  * createGraph(self, vertexes, edgesToVertexes) - metoda vytvoří graf ze zadaných vrcholů. Vertexes je pole objektů typu Vertex a edgesToVertexes je pole typu Edge.
  * getVertexes(self) - metoda vrátí vrcholy, nad kterými je možné provést Dijkstrův algoritmus. TJ vrcholy, které jsou vytvořeny pomocí metody init.
  * computePath(self, sourceId) - metoda nalezne nejkraští cesty ze zadaného vrcholu 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 o zadaného vrcholu.
  * getShortestPathTo(self,targetId) - metoda vrátí list vrcholů, přes které vede z vrcholu, nad kterými byla spuštěna operace computePath do vrcholu specifikovaného v targetId.
  * resetDijkstra(self) - tato metoda vyresetuje 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

Pozn: 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.

Pozn2: 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?200|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}}

<note warning>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.

Bodování je rozděleno do několika částí - viz sekce bodování. V případě 3.bodu jsou vám zadávány náhodně generované grafy. U těchto grafů se může stávat, že nebudou spojté. V případě nespojtého grafu provádíte operace pouze nad částmi, které jsou spojté.

<note important>Kromě správnosti řešení testujeme také jeho výkon. Hranice jsou nastaveny dostatečně vysoko, ale vzhledem k tomu, že jde o první testování výkonu tak bychom vás chtěli požádat aby jste v případě, že vám řešení neprochází na čas napsali na fóru.</note>

<note warning>K vyhodnocení používáme python verze 3.</note>

==== Bodování ====
Úloha je hodnocena osmi body. Body jsou vám udělovány následovně:
  - Funguje vám správně část Dijkstry, která počítá minimální vzdálenosti na základních datech - 2b
  - Funguje vám správně část Dijkstry, která počítá minimální vzdálenosti a nejkratší cestu základních datech - 2b
  - Funguje vám správně část Dijkstry, která počítá minimální vzdálenosti a cesty na náhodných grafech - 4b

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