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 de sectie in de cursus over “Bepalen van kortste paden”).
Implementeer het algoritme van Dijkstra in Java 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 gegeven interface PathFinder1 met een klasse Dijkstra. Hiervoor schrijf je een methode public List<Node<String>> shortestPath(DirectedGraph<String> graph, Node<String> source, Node<String> dest) die het kortste pad van source naar dest in (gerichte!) graaf graph teruggeeft. De eerste en laatste toppen in dit pad zijn respectievelijk source en dest. Als er meerdere mogelijke (kortste) paden zijn, maakt het niet uit welk pad je terug geeft. Zijn er geen paden van source naar dest, dan geef je null terug.
Zoals steeds kan je met behulp van klasse SimpleTest2 jouw code lokaal testen. Links naar de gebruikte grafenbibliotheek3 en de relevante documentatie4 staan in deze zin.