Hallo zusammen! Ich hoffe, es kann mir jemand etwas Hilfestellung geben.
Aufgabe:
Ich soll ein Programm namens JourneyPlaner als Konsolenanwendung schreiben, das eine S-Bahn-Verbindung zwischen zwei beliebigen Bahnhöfen im Berliner S-Bahn-Netz finden und auf der Kommandozeile ausgeben kann und dabei das Prinzip des Backtracking anwenden. Start- und Zielbahnhof sollen auf der
Kommandozeile übergeben werden können. Verwendung soll folgender kleiner Ausschnitt des S-Bahn-Netzes mit den Bahnhöfen Hauptbahnhof, Friedrichstraße, Westkreuz, Gesundbrunnen, Südkreuz, Adlershof und den Bahnen S45 zwischen Südkreuz und Adlershof, S1 zwischen Gesundbrunnen,Friedrichstraße und Südkreuz, S5 zwischen Hauptbahnhof und Friedrichstraße, S41 bzw. S42 zwischen Südkreuz und Westkreuz und S75 zwischen Hauptbahnhof und Westkreuz. Zur Beschreibung des Streckennetzes folgende Arrays sollen folgende Arrays genutzt werden, wobei das erste Array die Bahnhöfe und das zweite die Verbindungen repräsentiert. Die Spalten bzw. Zeilen des zweiten Arrays entsprechen den Bahnhöfen in der Reihenfolge des ersten Arrays. Ein Eintrag > 0 beschreibt die jeweilige S-Bahn, die zwischen zwei Bahnhöfen
verkehrt.
String[] stations = {
"Hauptbahnhof", "Friedrichstraße",
"Westkreuz", "Gesundbrunnen",
"Südkreuz", "Adlershof"};
int [][] lines = {
{0, 5, 75, 0, 0, 0},
{5, 0, 0, 1, 1, 0},
{75, 0, 0, 0, 42, 0},
{0, 1, 0, 0, 0, 0},
{0, 1, 41, 0, 0, 45},
{0, 0, 0, 0, 45, 0}
};
- lines[0][2] bedeutet, dass zwischen Hauptbahnhof (Index 0) und Westkreuz (Index 2) die Linie S75 verkehrt (und umgekehrt: lines[2][0] ).
- lines[2][4] bedeutet, dass zwischen Westkreuz (Index 2) und Südkreuz (Index 4) die Linie S42 verkehrt.
- Umgekehrt verkehrt die Linie S41 (lines[4][2] ).
Der Aufruf des Programms und die Ausgabe sollen folgendermaßen aussehen:
java JourneyPlaner Friedrichstraße Adlershof
Friedrichstraße -> Südkreuz mit S1
Südkreuz -> Adlershof mit S45
Hinweis: Es soll ein Array verwendet werden, in dem gespeichert wird, welche Stationen bereits besucht wurden, um Zyklen zu verhindern. Außerdem soll eine verwendet Liste, in der die Information gespeichert wurden, von welcher Station ich zu welcher Station mit welcher Linie gefahren bin, und geben den Inhalt der Liste anschließend auf der Konsole ausgeben. Die Signatur der Methode könnte folgendermaßen aussehen:
boolean solve( int start, int ziel, boolean [] besucht, List<String> tour);
- Der Parameter start bezeichnet den Bahnhof, an dem Sie sich gerade
befinden. - Der Parameter ziel bezeichnet den Bahnhof, den Sie erreichen wollen
- Der Parameter besucht enthält die Information, welche Bahnhöfe Sie
bereits besucht haben. - Der Parameter tour enthält alle zurückgelegten Teilstrecken (z. B.
Friedrichstraße -> Südkreuz mit S1)
Zusatzaufgabe B1 (5 Punkte)
Erweitern Sie das Programm JourneyPlaner so, dass immer die Strecke mit den wenigsten Zwischenhalten bzw. Bahnwechseln zwischen zwei Bahnhöfen gefunden wird. Zum Beispiel gibt es für die Strecke vom Westkreuz zum Südkreuz mindestens zwei Möglichkeiten:
Westkreuz -> Hauptbahnhof mit S75
Hauptbahnhof -> Friedrichstraße mit S5
Friedrichstraße -> Südkreuz mit S1
und
Westkreuz -> Südkreuz mit S42
Von den beiden Möglichkeiten soll nur die zweite auf der Konsole ausgegeben werden, da diese im Gegensatz zur ersten keinen Bahnwechsel erfordert. Hinweis: Versuchen Sie alle Möglichkeiten aus, auch wenn Sie bereits einen Weg gefunden haben und nehmen Sie dann die Möglichkeit mit den wenigsten Stationen. Wichtig: Sie dürfen die vorgegebenen Arrays nicht ändern!
Einige Sachen habe ich schon fertig. Nur ich verstehe die Aufgabe der Zyklenvermeidung nicht.
Es wäre super, wenn sich jemand melden würde. Vielen Dank.