Pfade in gerichteten Graphen finden
-
Hallo zusammen,
ich habe gerade das Problem, das ich nicht genau weiß, wonach ich suchen muss, um mit dem folgenden Problem weiter zu kommen:
Ich habe einen gerichteten und gewichteten Graphen. Die Gewichte aller Verbindungen sind entweder +1 oder -1, das Gewicht eines Pfades ist als Produkt der Einzelgewichte definiert (also ebenfalls +/-1).
Was ich nun suche sind alle Pfade von einem Knoten I zu einem Knoten J. Der Hintergrund ist, dass ich vergleichen möchte ob alle Pfade von I nach J das gleiche Gewicht haben oder nicht, also ob man eine art Netto-Gewicht von I nach J angeben/definieren kann.
Die Suche nach "Pfade in Graphen finden" oder ähnliches ergibt immer nur Algorithmen zum auffinden des kürzesten Weges (z.B. Dijkstra-Algorithmus). Hier ist aber nicht sichergestellt, dass tatsächliche alle Wege gefunden werden.
Hat jemand Anregungen oder zumindest Stichworte nach denen man noch suchen könnte um dieses Problem anzugehen?
Vielen Dank schonmal
Grüße
foxx
-
Das Enumerieren aller möglichen Wege ist eigentlich recht einfach: du machst eine Tiefen- oder Breitensuche, und jedesmal, wenn du am Zielknoten angekommen bist, speicherst du den aktuellen Verlauf. Und natürlich verfolgst du nicht die Unterknoten des Zielknotens weiter.
Es könnte allerdings sein, daß es effizientere Wege gibt, das zu lösen.
-
Hallo,
vielen Dank für die Antwort, habe es hinbekommen. Tiefensuche war das Stichwort, das die Lösung bereithielt
Grüße
foxx