Het bepalen van kortste paden in een graaf is een vaak voorkomend probleem met eindeloos veel toepassingen. Denk bijvoorbeeld aan de tegenwoordig overal aanwezige GPS systemen en Google Maps die in een mum van tijd de optimale route tussen twee willekeurige plaatsen ergens op de wereld kunnen berekenen. Uiteraard worden hiervoor geavanceerde algoritmes gebruikt maar velen steunen nog steeds op het oorspronkelijke idee van Dijkstra (zie sectie 10.3 in het handboek, “Bepalen van korste paden”).

Implementeer het algoritme van Dijkstra in Python voor het bepalen van een kortste pad van een gegeven top u naar een bestemming v in een gerichte, gewogen graaf G. Alle gewichten zijn positief, zoals vereist voor een correcte werking van het algoritme. Let wel: de graaf is niet gegarandeerd samenhangend.

Besteed voldoende aandacht aan de efficiëntie van je implementatie. Vermijd bijvoorbeeld zeker dat het bepalen van de top met het kleinste label in elke stap lineaire tijd kost, door gebruik te maken van een geschikte datastructuur. Bovendien berekent het algoritme zoals beschreven in het handboek een kortste pad van de gegeven top u naar alle andere toppen in de graaf. Aangezien we hier enkel het kortste pad naar een gegeven andere top v wensen, kan je het algoritme vroegtijdig laten stoppen. Denk er goed over na wanneer je de berekeningen kan afbreken.

Implementeer een functie shortest_path(graph, src, dest) die een lijst moet teruggeven die het gewogen korste pad van src naar dest in graph bevat.

Jullie krijgen alvast een implementatie van een prioriteitswachtlijn. Bij het initialiseren van een object van de klasse PriorityQueue kan er een optionele parameter sortkey meegegeven worden. Als je wil dat een element x voor een element y komt in deze wachtlijn, moet je ervoor zorgen dat het resultaat van de oproep sortkey(x) kleiner is dan het resultaat van de oproep sortkey(y).

We maken bij deze oefening gebruik van een eenvoudige grafenbibliotheek graphlib. De API van de deze bibliotheek vind je hier¹. Neem eerst en vooral eens de API en de bibliotheek zelf door en stel eventueel vragen hierover voor je begint te programmeren.

Belangrijke opmerking: om met de grafenbibliotheek te kunnen werken in PyCharm moet je het bestand graph_library.py² toevoegen aan dezelfde directory als waarin je ze gebruikt. Dan kun je ze gebruiken door ze te importeren met

from graph_library import *

Dit import statement mag wel niet mee ingediend worden op dodona.

Voorbeeld:

>>> graph = directed_graph_from_dict({'Alice': ['Bob'], 'Bob': ['Carol'], 'Carol': ['Alice']}, weights = {('Alice', 'Bob'): 5, ('Bob', 'Carol'): 5, ('Carol', 'Alice'): 5})
>>> src = graph.get_node_from_name('Carol')
>>> dest = graph.get_node_from_name('Alice')
>>> shortest_path(graph, src, dest)
[Node('Carol'), Node('Alice')]