Preprocess kürzeste Pfade unter Konkurrenz

Question

Es ist leicht zu beweisen, dass, wenn P ist ein kürzester Weg zwischen u und v, dann ist jeder Teilweg auch ein kürzester Weg. ein zusammenhängendes Graphen Gegeben, ich mag eine der kürzesten Weg zu Vorprozess zwischen jedem Paar von Knoten in einer Matrix, so dass:

1. Pfad [u, v] = Pfad [v, u]
2. Wenn x , y in Pfad [u, v] dann Pfad [x, y] ist ein Unterpfad von Pfad [u, v].

Ich kann einen Algorithmus oder einen Beweis nicht herausfinden und tatsächlich weiß ich nicht, ob das möglich ist. Jede Idee ist willkommen. Danke.

Answer 1

Sie können nur (1) erhalten, wenn Sie mit ungerichteten Graphen arbeiten ODER wenn sichergestellt ist, dass das Gewicht des Bogens (a, b) gleich dem Gewicht des Bogens (b, a) für alle Bögen ist in deinem Diagramm.

Das von Ihnen beschriebene Problem klingt wie das kürzeste Pfadproblem aller Paare: Suchen Sie für jedes Knotenpaar in einem verbundenen Diagramm die kürzesten Pfade zwischen Knoten im Paar. Der Floyd-Warshall-Algorithmus kann verwendet werden, um die Längen von Pfaden zu finden, und es ist einfach, die kürzesten Wege von dort zu rekonstruieren.

Dieser Algorithmus erfordert außerdem, dass es keine negativen Zyklen gibt (andernfalls könnte man immer einen kürzeren Pfad erhalten, wenn man diesen Zyklus erneut durchläuft), aber diese Anforderung erscheint vernünftig.

Um die Eigenschaft (2) zu garantieren, müssen Sie beim Rekonstruieren von Pfaden sicherstellen, dass "kanonische" Pfade immer dann rekonstruiert werden, wenn mehr als ein kürzester Pfad möglich ist. Um dies zu tun, erzwinge eine Ordnung auf den Knoten und teste immer Kandidatenknoten in aufsteigender Reihenfolge, wobei immer der Knoten mit der niedrigsten Ordnung bevorzugt wird, der die Eigenschaft des kürzesten Pfads beibehält.

Wikipedia hat eine ziemlich gute Zuschreibung.