Das Programm findet den kürzesten Weg zwischen zwei Punkten auf einem nxn Schachfeld, den ein Springer gehen kann, mit Hilfe des Dijkstra Algorithmus. Eingabewerte sind Schachfeldgröße, Start-, und Endpunkt.
- Adjazenzmatrix erstellen
- über alle Felder iterieren (in 2d matrix)
- jedes Feld mit dem erreichbaren verknüpfen (an entsprechender Stelle auf der Matrix 1 eintragen) Wichtig: von 2d auf 1d indexierung rechnen
- startpunkt zu ausgangspunkte hinzufügen
- Aus ausgangspunkte den Punkt mit kleinstem Wert suchen -> "aktueller Punkt"
- Punkte durcharbeiten, die in Adjazenzmatrix mit "1" mit dem aktuellen Punkt verbunden sind
- Vergleiche jeweils, ob bisheriger Knoten.wert im Knotenarray größer als der aktuelle+dem des aktuellen Nachfolgerknotens aus Matrix ist. wenn größer, setze Knotenwert auf aktuellerKnoten.wert+Matrixwert und setze den Vorgänger neu. wenn kleiner, lass den alten wert.
- NachfolgerPunkt in ausgangspunkte hinzufügen. aktuellen Punkt aus ausgangspunkte entfernen. Schritte wiederholen
- Abbruch wenn ausgangspunkte leer
- Endpunkt betrachten und jeweils den vorgänger merken -> daraus ergibt sich kürzester Weg
- Ausgangspunkte ist eine arraylist, in der die Indizes der noch zu behandelnden Punkte gespeichert sind
- Knoten hat die Eigenschaften: Vorgängerindex; wert (=Gewicht/Strecke)
- Nummerierung immer von 0 beginnend
- 2 Nummerierungssysteme: Koordinatensystem beim Schachfeld; Durchnumeriertes Schachfeld (Achsen bei Adjazenzmatrix)
- "Punkt" = Knotenname = Nummer auf Schachbrett = index in Adjazenzmatrix
- adjazenzmatrix erstellen:
Adjazenzmatrix aMatrix = new Adjazenzmatrix(feldGroesse);aMatrix.befuellen0();aMatrix.befuellenSpringermuster(); - Dijkstra berechnen (in der Liste stehen dann in der Reihenfolge die besuchten Felder drinnen):
ArrayList Ergebnis = dijkstra(aMatrix, Anfangsfeld, Endfeld);