Search
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
Vytvořte soubor dijkstra.py a v něm vytvořte následující třídy:
dijkstra.py
Třída reprezentující hranu v grafu. Tato třída má následující atributy:
source
target
weight
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().
__init__(self, source, target, weight)
__init__()
createGraph()
Třída reprezentující vrchol v grafu. Tato třída má následující atributy:
id
name
edges
minDistance
computePath()
previousVertex
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.
__init__(self, id, name)
Třída reprezentující Dijkstrův algoritmus. Tato třída má pouze jednu proměnnou
vertexes
Třída má tyto metody:
createGraph(self, vertexes, edgesToVertexes)
Vertexes
Vertex
edgesToVertexes
Edge
getVertexes(self)
computePath(self, sourceId)
sourceId
getShortestPathTo(self, targetId)
targetId
resetDijkstra(self)
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')
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.
Dijkstra()
getVertexes()
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ů).