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 (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 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í 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().

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.

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

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.

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