Der modifizierte kürzeste Weg unter Verwendung von Dijkstra oder Bellman -Ford -Algorithmus

Question

Wie können wir Dijkstra oder Bellman -Ford -Algorithmus verwenden, um den kürzesten Weg in einem Diagramm zu finden, dessen einige der Kanten betroffen sind, wenn wir bestimmte Scheitelpunkte gehen? So dass die Länge der betroffenen Kante mehr als die ursprüngliche Länge ist.

Answer 1

Wenn ich dieses Recht verstehe, möchten Sie die Kosten einer Kante in einem Diagramm ändern, abhängig von Knoten, die in Ihrem aktuellen Pfad besucht werden. Ein Beispiel aus den Kommentaren ist:

"Edge AB hat Länge 3, aber wenn Sie auch den Knoten C besuchen, beträgt ABs Länge 5"

Jetzt scheint es keine Möglichkeit zu geben, dass der Algorithmus von Djikstra verwendet wird, da es einen gierigen Schritt in diesem Algorithmus gibt, der den besten Knoten in jeder Phase auswählt. Die Vorstellung, dass sich der "beste" Knoten zu diesem Zeitpunkt zu einem späteren Zeitpunkt (aufgrund einer Regel wie oben) ändern kann Ich bin mir nicht sicher, ob dies NP schwierig ist, wie dies vorgeschlagen ist, aber es kann von Anfang an keinen Dijikstra -Ansatz verwenden. +1 für das Problem.