Mit der Tiefensuche alle Wege finden

[Guest]

Huhu!

Ich habe vor, eine Tiefensuche zu machen, um alle Wege in einem Graphen, zwischen zwei verschiedenen Orten zu finden.
Den Algorithmus zum Finden von einem Weg(den kürzesten), hab ich bereits implementiert, der funktioniert auch.

Jetzt hab ich die Idee, dass ich die schon benutzten Wege komplett speicher, und dann *irgendwie* vergleiche, ob ich diesen Weg schon hab, oder nicht. Allerdings fällt mir dazu auch keine Abbruchbedingung und/oder eine Vergleichsmöglichkeit ein :|

Hat jemand vllt eine Idee, wie man meinen Algorithmus komplettieren könnte? Hab ich überhaupt den richtigen Ansatz?

Vielen Dank im voraus für die Hilfe,
lg, lyx

 

[WeirdAl]

Hi,
wenn Start und Zielort gegeben sind, kannst Du das Ergebnis der Suche mit einem Start/Ziel Key und der Strecke (Liste von Punkten oder so) als Value in eine HashMap ablegen. Dann siehst Du vor dem durchlaufen deines Graphen in der Liste nach, ob es eine Start/Ziel Kombination schon in der Hashmap gibt.

 

[Marco13]

Wenn der Graph einen Zyklus enthält, gibt es u.U. unendlich viele solcher Wege. Und wenn es nicht unendlich viele gibt (weil du keinen Weg zweimal gehst, was man (glaubich!?) eigentlich "inhärent" in die Tiefensuche einbauen könnte) verstehe ich die Frage nicht...