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 ShortestPaths findShortestPaths(double[][] adjacency). De input van deze methode is een tweedimensionale array (de adjacentiematrix) waarbij adjacency[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 ShortestPaths.

Het type ShortestPaths 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 ShortestPaths te implementeren schrijf je de methode public double getShortestPathLength(int from, int to) en de methode public List<Integer> getShortestPath(int from, int to). 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 findShortestPaths als input krijgt aan te passen. Indien je dit wel doet, zal de test falen.