Gegeven is een graaf \((V,E)\) met toppen \(V\) en gerichte, gewogen bogen \(E\). We zoeken hierin het kortste pad van een gegeven starttop naar een gegeven bestemming.

Het algoritme van Dijkstra gaat er van uit dat alle gewichten positief zijn. Indien er ook negatieve gewichten voorkomen, garandeert de gretige aanpak van Dijkstra immers niet dat het correcte kortste pad gevonden wordt. Het algoritme van Bellman en Ford is een variant van Dijkstra die wel met negatieve gewichten omkan. De prijs die daarvoor betaald wordt, is een verhoogde tijdscomplexiteit.

In een graaf met sommige negatieve gewichten kan er eventueel een negatieve cykel voorkomen, d.w.z. een cykel waarvan de som van de gewichten van de bevatte bogen negatief is. Indien zo’n cykel bereikbaar is vanuit de starttop, is het kortste pad ongedefinieerd. We kunnen immers het totale gewicht van elk pad dat deze cykel bevat arbitrair klein maken door herhaaldelijk de cykel te doorlopen. Het algoritme van Bellman en Ford kan dergelijke negatieve cykels ook detecteren en geeft dan een gepaste foutmelding.

Net zoals bij Dijkstra, wordt de afstand van de starttop tot elke andere top benaderd en iteratief bijgestuurd tot ze convergeert naar de effectieve kortste afstand. Het bijsturen gebeurt hier bovendien ook via hetzelfde mechanisme: we nemen een boog \((u,v)\) en kijken of we een kortere weg naar \(v\) gevonden hebben door via \(u\) te gaan. Bij Dijkstra worden stap voor stap alle uitgaande bogen verwerkt van de tot dan toe nog niet bezochte top met minimale afstand (gretig). Elke boog wordt dus slechts eenmaal bekeken. Dit is echter niet voldoende wanneer er negatieve gewichten voorkomen.

Bij Bellman-Ford worden de updates \(\lvert V \lvert -1\) keer toegepast voor alle bogen (in arbitraire volgorde). Na de \(i\)-de update, hebben we zo reeds alle kortste paden gevonden bestaande uit hoogstens \(i\) bogen. Aangezien elk mogelijk pad zonder cykel hoogstens \(\lvert V \lvert -1\) bogen bevat, moeten we dus precies zoveel keer alles updaten om zeker te zijn dat het kortste pad gevonden is. Vervolgens updaten we nog een laatste keer en als dit resulteert in enige wijziging, hebben we een negatieve cykel gevonden (denk erover na waarom dit zo is).

De pseudocode ziet er als volgt uit:

function BellmanFord(graph, source, destination)
   
   distance = []
   predecessor = []

   // stap 1: initialisatie
   for each vertex v in graph.vertices:
      predecessor[v] = null
      if v is source:
         distance[v] = 0
      else:
         distance[v] = inf

   // stap 2: herhaaldelijk updaten
   for i from 1 to size(graph.vertices)-1:
      for each edge (u,v) in graph.edges:
         w = edge.weight
         if distance[u] + w < distance[v]:
            distance[v] = distance[u] + w
            predecessor[v] = u

   // stap 3: check negatieve cykel
   for each edge (u,v) in graph.edges:
      w = edge.weight
      if distance[u] + w < distance[v]:
         error "Graaf bevat een negatieve cykel"
           
   // stap 4: reconstrueer korste pad
   vertex = destination
   path = [destination]
   while vertex != source:
      vertex = predecessor[vertex]
      if vertex == null:
         error "Bestemming onbereikbaar uit starttop"
      path = [vertex, path]
   		
   return path

Implementeer dit algoritme in een klasse BellmanFordKortstePaden die de gegeven interface KortstePaden¹ implementeert door de methode public List<Node> kortstePad(DirectedGraph graaf, Node start, Node bestemming) te schrijven. Deze methode neemt een graaf, de starttop en de eindtop als input. Als output geeft het algoritme een lijst terug waarin de bezochte toppen langs het kortste pad, in de juiste volgorde, worden opgeslagen. Indien er tussen start en bestemming geen pad bestaat, wordt er een UnreachableDestinationException opgegooid. Indien er een negatieve cykel aanwezig is in de graaf, wordt er een NegativeCycleException opgegooid. Beide excepties zijn gedefinieerd in de interface KortstePaden².

We maken bij deze oefening gebruik van een eenvoudige grafenbibliotheek graphlib. Deze bevat onder meer de klassen DirectedGraph en Node. De API van deze bibliotheek vind je hier³. Een andere interessante klasse is DirectedEdge, die ook van pas kan komen tijdens het oplossen van de oefening. Neem eerst en vooral eens de API door en stel eventueel vragen hierover voor je begint te programmeren.

Opmerkingen:

• Om met de grafenbibliotheek te kunnen werken in IntelliJ, moet je het bestand graphlib.jar⁴ toevoegen aan je project. Hiervoor ga je naar File -> Project Structure…. Vervolgens kies je Libraries en klik je op de knop met het plusteken (+). Kies voor Java en navigeer naar het gedownloade bestand graphlib.jar⁵.
• Pas de graaf uit de input van het algoritme niet aan. Indien je dit wel doet, zullen je testen falen.

Extra: het is mogelijk om de berekeningen soms vroegtijdig te stoppen. Denk er over na wanneer dit kan en voer de nodige wijzigingen door in het algoritme. Wat is de asymptotische tijdscomplexiteit van het originele en gewijzigde algoritme?

Gebruik eventueel de testklasse SimpleTest⁶ om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.