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.
heapq
, queue
a podobně) bude práce hodnocena jako neodevzdaná (a to i zpětně)!
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ů).