2016-05-26 17 views
-1

Ich habe eine Frage zu Dijkstra und/oder DFS. Nehmen wir an, ich habe ein Diagramm mit mehreren Knoten und Kanten. Jetzt möchte ich einen Pfad von Knoten A zu Knoten B finden. Auf diesem Weg muss ich bestimmte Kanten nehmen, zum Beispiel die Kante (C, D).Nehmen Sie bestimmte Kanten in Dijkstra (oder DFS)

Edit:

Sorry, wenn es ein wenig unklar war. Meine Frage ist: Ich möchte einen Pfad von A nach B. Gibt es einen Pfad, so dass alle Kanten {a, b}, {b, c} ... und so weiter genommen werden? Ich bin interessiert, ob das mit dfs möglich ist. Und wenn das auch mit Dijkstra unter derselben Bedingung möglich ist, wenn ich den kürzesten Weg von A nach B haben möchte und einige Kanten {a, b}, {b, c} im Graphen benötigt werden. Auch das Diagramm ist gerichtet.

Hilfe würde wirklich geschätzt werden!

+0

Was ist die Frage genau? –

+0

Wenn eine Kante '{a, b}' auf dem kürzesten Weg von 's' nach' t' benötigt wird, wäre es die Lösung, einen kürzesten Weg von 's' nach' a' und einem kürzesten Weg zu finden Pfad von "b" nach "t" und kombinieren Sie die Pfade mit '{a, b}' in der Mitte. – Codor

+0

Was genau meinen Sie mit "anfänglich ungewichtet"? Wenn dies der Fall ist, was ist der kürzeste Weg? Einer mit einer minimalen Anzahl von Kanten? Wenn ja, wäre das Kantengewicht implizit "1". – Codor

Antwort

0
  1. Erstellen Sie eine Liste aller Kanten, die Sie sicherstellen möchten, dass navigiert werden muss.

  2. Führen Sie ein DFS von der Quelle aus aus.

  3. Jedes Mal, wenn Sie eine in der Liste enthaltene Kante passieren, wird die Markierung als "traversiert" markiert.

  4. Wenn Sie das Ziel erreicht haben, prüfen Sie, ob alle Kanten in der Liste als durchlaufen markiert sind.
    a.) Wenn ja, Zielzustand erreicht.
    b.) Andernfalls können Sie jede Kante in der Liste zurück- und aufheben, während Sie sie durchlaufen.