10. úkol - Dijkstra

Vaším desátým úkolem je naimplementovat Dijkstrův algoritmus a použít ho k hledání nejkratších cest v grafu (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.

Vytvořte soubor dijkstra.py (můžete využít šablonu dijkstra.py) a v něm vytvořte následující třídy:

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:

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

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

__init__(self,id,name)

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

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')

Vzhledem k delšímu zápisu příkladu použtí je příklad umístěn v souboru dijkstrause.py.

Níže je graf, který by vám měl vzniknout po správné konstrukci přiloženého příkladu:

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. dijkstrause.py

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

Úloha je hodnocena osmi body. Body jsou vám udělovány následovně:

1. Funguje vám správně část Dijkstry, která počítá minimální vzdálenosti na základních datech - 2b
2. Funguje vám správně část Dijkstry, která počítá minimální vzdálenosti a nejkratší cestu základních datech - 2b
3. Funguje vám správně část Dijkstry, která počítá minimální vzdálenosti a cesty na náhodných grafech - 4b

Úterní cvičení: 2.1.2018

Páteční cvičení: 5.1.2018

Vždy před začátkem vašeho cvičení.