Het algoritme van Floyd gebruikt dynamisch programmeren om de kortste paden tussen elk paar toppen in een graaf tegelijk te berekenen. We starten van een adjacentiematrix adj, die het gewicht bevat van de bogen tussen elk paar toppen. Het gewicht van ontbrekende bogen wordt als oneindig genoteerd. Het algoritme van Floyd gaat dan als volgt:

dist ← adj
for k from 1 to |dist|
   for i from 1 to |dist|
      for j from 1 to |dist|
         if dist[i][j] > dist[i][k] + dist[k][j] 
            dist[i][j] ← dist[i][k] + dist[k][j]
         end if

Implementeer dit algoritme. Zorg ervoor dat niet enkel de lengte van de kortste paden berekend wordt, maar dat je ook de paden zelf kan reconstrueren door extra hulpdata op te slaan.

Hiervoor implementeer je de interface Routeplanner¹ in een klasse genaamd FloydRoutePlanner. Deze bevat een methode public KortstePaden berekenKortstePaden(double[][] adjacentie). De input van deze methode is een tweedimensionale array (de adjacentiematrix) waarbij adjacentie[i][j] de afstand van de top met nummer \(i\) naar de top met nummer \(j\) bevat. De output is een object van van het type KortstePaden.

Het type KortstePaden vind je terug als binneninterface in de interface Routeplanner. Implementeer deze interface in een binnenklasse van de klasse FloydRoutePlanner. De naam van deze klasse mag je zelf kiezen. Om de binneninterface KortstePaden te implementeren schrijf je de methode public double getKortstePadLengte(int top1, int top2) en de methode public List<Integer> getKortstePad(int top1, int top2). De input van zowel de eerste methode als de tweede methode zijn twee topnummers. De output van de eerste methode is de lengte van het kortste pad tussen de twee toppen. De output van de tweede methode is het kortste pad, voorgesteld als een lijst van toppen.

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

Opmerking

Het is niet toegestaan om de adjacentiematrix die de methode berekenKortstePaden als input krijgt aan te passen. Indien je dit wel doet, zal de test falen.