Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

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.

Při použití externích knihoven (např. heapq, queue a podobně) bude práce hodnocena jako neodevzdaná (a to i zpětně)!

Zadání

Vytvořte soubor dijkstra.py a v něm vytvořte následující třídy:

Můžete použít tuto šablonu: dijkstra.py

Edge

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


Vertex

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.


Dijkstra

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

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

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

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

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.

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.

Implementujte Dijkstrův algoritmus. Použití jiného algoritmu bude hodnoceno 0 body(a to i zpětně)!

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

Kromě správnosti řešení testujeme také jeho výkon. Hranice jsou nastaveny dostatečně vysoko, ale v případě, že vaše řešení neprochází na čas, spojte se s cvičícím.

Bodování

Úloha je hodnocena max. 8 body, které jsou 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: 2 body
  2. Funguje vám správně část Dijkstry, která počítá minimální vzdálenosti a nejkratší cestu základních datech: 2 body
  3. Funguje vám správně část Dijkstry, která počítá minimální vzdálenosti a cesty na náhodných grafech: 4 body
courses/b6b36zal/zadani/10_dijkstra.txt · Last modified: 2020/12/31 10:27 by seredlad