Shortcut links:
Basic graph definitions
Basics of shortest paths (this page)
Path lengths and distances
Sei 𝐺 = (𝑉, 𝐴) ein einfacher, gerichteter Graph und für jede Kante 𝑎 ∈ 𝐴 sei 𝑙(𝑎) eine reale Nummer und die Länge von 𝑎.
- Die Länge von einem gewöhnlichen Path (inklusive gewöhnliche cycles) ist die Summe von den Längen von allen Kanten in diesem Path.
- Abhängig vom Kontext, die Länge von einem generalized Path (inklusive generalized cycles) ist entweder definiert identisch zu gewöhnlichen Pathen, oder die Länge der backwards Kanten werden nicht addiert, sondern subtrahiert.
- Wenn die Länge von einem gewöhnlichen oder generalizedn Cycle negativ ist, wird dieser Cycle einen negativen cycle genannt.
- Für zwei Knoten 𝑠,𝑡 ∈ 𝑉, ein kürzester Path von 𝑠 nach 𝑡 ist ein (𝑠,𝑡)-path mit minimaler Länge von allen (𝑠,𝑡) Pathe.
- Die Distance von 𝑠 nach 𝑡 ist:
- +unendlich wenn kein (𝑠,𝑡)-path existiert;
- -unendlich wenn es einen negativen cycle entlang (𝑠,𝑡)-path gibt;
- Die Länge von einem kürzesten (𝑠,𝑡)-path sonst;
Note:
In diesem Kontext sind ungerichtete Graphen als symmetrische gerichtete Graphen anzusehen, so dass zwei gegensätzlich gerichtete Kanten die selbe Länge haben.
Wenn es keine negativen cycles gibt, ist die Distanz von einem Knoten zu sich selbst 0, weil der triviale Path ohne keinen die Länge 0 hat. Auf der anderen seite, wenn ein Knoten in einem negativen cycle ist, ist seine Distanz zu sich selbst -unendlich.
Weil durch den negativen cycle ja immer ein Weg mit einer noch kürzeren Länge gefunden werden kann. Und negativ ist kleiner als Null.
Subpath property of shortest paths
Statement: Für zwei Knoten 𝑠,𝑡 ∈ 𝑉, sei 𝑝 ein kürzester (𝑠,𝑡)-Path. Seit 𝑣,𝑤 ∈ 𝑉 zwei Knoten auf dem Path 𝑝, so dass 𝑣 vor 𝑤 liegt. Dann ist der subpath von 𝑝, von 𝑣 zu 𝑤 ein kürzester (𝑣,𝑤)-Path.
Beweis: Seien 𝑝1, 𝑝2 und 𝑝3 die Subpathe von 𝑝 von 𝑠 nach 𝑣, von 𝑣 nach 𝑤 und von 𝑤 nach 𝑡. Für einen Widerspruchsbeweis angenommen, es gibt einen (𝑣,𝑤)-paht 𝑝2' der kürzer ist als 𝑝2. Dann würde die Aneinanderreihung der Pathe 𝑝1+𝑝2'+𝑝3 einen kürzeren (𝑠,𝑡)-path als 𝑝 ergeben. Da 𝑝 aber schon der kürzeste (𝑠,𝑡)-path ist, ist dies ein Widerspruch.
Die Subpathe eines kürzesten Pathes sind ebenfalls kürzeste Pathe.
Anmerkung: Gewöhnlich wird nur der Fall v=s beachtet. Also dass es nur zwei Pathe gibt und die Argumentation mit dem ersten Path gemacht wird. Diese Version wird auch prefix property genannt.
Valid distance property
Definition: Für jeden Knoten 𝑢 ∈ sei 𝑑(𝑢) eine real Zahl. Irgendeinen Zahl, muss nicht die Distanz sein. Das valid distance property wird erfüllt, wenn 𝑑(𝑤) ≤ 𝑑(𝑣) + l(𝑣,𝑤) für alle Kanten (𝑣,𝑤) ∈ 𝐴.
Das ist einfach so eine Definition.
Statement: Sei 𝑠 aus 𝑉 und für jeden Knoten 𝑢 aus 𝑉 sei d(𝑢) die Distanz von 𝑠 nach 𝑢 unter Beachtung der Kantenlängen 𝑙.
Es sei d(𝑤) ≤ d(𝑣) + 𝑙(𝑣,𝑤) Für alle Kanten (𝑣,𝑤) aus 𝐴.
Das valid distance property ist erfüllt für kürzeste Wege mit Kantenlängen im Graph.
Heißt auf gut deutsch, dass es eine "kürzeste" Kante von 𝑣 nach 𝑤 gibt und alle anderen Kanten von 𝑣 nach 𝑤 sind länger. Und da 𝑣 ja beliebig sein kann, heißt es: Es gibt einen kürzesten Weg nach 𝑤 und alle andern sind länger.
Beweis: The linke Seite der Ungleichung ist die Länge von dem kürzesten (𝑠,𝑤) Path.
Die rechte Seite ist die Länge von irgendeinem (𝑠,𝑤) Path (also die Aneinanderreihnug von dem kürzesten (𝑠,𝑣) Path und einer Kante (𝑣,𝑤))
Statement distance update: In den meisten shortest-path algorithmen, für jeden Knoten 𝑣 AUS V gibt es ein Attribut d(𝑣).
Dieses Attribut entspricht die Länge von einem (s,𝑣) Path und ist die echte Distanz von s zu 𝑣 wenn der Algorithmus terminiert.
In praktisch allen standard Algorithmen, die folgende Update Operation ist die (einzige) Operation zum updaten des d-Attributs:
1. Wähle eine Kante (𝑣,w) AUS A
2. Wenn (𝑣,w) das valid distance properts verletzt, also diese Kante einen kürzeren Weg zu w ermöglicht, also d(w) > d(𝑣) + l(𝑣,w) dann setzte d(w) := d(𝑣) + l(𝑣,w)
Distances along shortest paths
Sei 𝑠 ∈ 𝑉 und für jeden Knoten 𝑢 ∈ V sei d(𝑢) die Distanz von 𝑠 nach 𝑢 unter Berücksichtigung der Kantenlängen 𝑙.
Statement: Angenommen es gibt keine negativen Cyclen. Für eine Kante (𝑣,𝑤), es ist d(𝑤) = d(𝑣) + 𝑙(𝑣,𝑤) genau dann wenn die Kante (𝑣,𝑤) die letzte Kante von einem kürzesten (𝑠,𝑤) Path ist.
Beweis:
- Fall d(w) = d(v) + l(v,w)
Dann hat die Aneinanderreihung von dem kürzesten Path von s nach v und (v,w) die Länge d(w) und damit die kürzeste Länge. (Weil die Kante (v,w) eben die letzte Kante im (s,w) Path ist. - Fall d(w) != d(v) + l(v,w)
Wegen dem valid distanz property ist d(w) < d(v) + l(v,w) (Wenn der Path nicht über die kürzeste kante geht, dann über eine Längere, also ist die Distanz auch größer als die kürzeste Distanz d(w)). Für einen Widerspruchsbeweis angenommen, dass ein kürzester (s,w) Path ist von der Form p + (v,w). Dann hat p die Länge d(w) - l(v,w) < d(v) was ein Widerspruch zur Definition von d(v) ist.
Reconstruction of a shortest path from the distances
Angenommen, dass für die Knoten 𝑠,𝑡 ∈ V die Distanz d𝑠(t) von 𝑠 to 𝑡 unter Beachtung der Kantenlängen l, welche eine reale Nummer ist (weder +inf noch -inf). Dann kann ein kürzester (𝑠,𝑡) Path 𝑝 wie folgt konstruiert werden.
- Initialisiere 𝑝 als leer
- Setzte 𝑤 := 𝑡 - Wir konstruieren den Path rückwärts von 𝑡 nach 𝑠
- While w /= s
- Finde eine Kante (𝑣,𝑤), so dass d𝑠(𝑤) = d𝑠(𝑣) + l(𝑣,𝑤)
- Füge die Kante (𝑣,𝑤) an den Anfang von 𝑝 an
- Setze 𝑤 := 𝑣
Constructing a shortest-paths arborescence or a negative cycle
Wie beim Valid distance property erwähnt, benutzen die meisten Algorithmen für das kürzeste Wege Probleme eine Standard Update Operation. Diese Operation kann wie folgt erweitert werden (mit 𝑠 für den Startknoten).
Jeder Knoten v ∈ V speichert eine von den incoming Kanten als zusätzliches Attribut:
- Initialisierung des Attributs:
Dieses Attribut wird für den Knoten s mit void initialisiert.
Für alle anderen Knoten v, die mit d(v) = +inf initialisiert wurden, wird dieses Attribut auch mit void initialisiert.Je nachdem ob die ausgehenden Kanten von s bei der Initialisierung beachtet, oder erst während der Iteration, ist die Distanz der abgehenden Knoten von s damit nicht +inf.
Und das zusätzliche Attribut dieser Knoten wird mit der initial incoming Kante (s,v) initialisiert. - Update: Wann immer die Standard Update Operation auf eine Kante (v,w) angewendet wird (also das Aktualisieren von der Distanz), wird diese Kante (v,w) die incoming Kante von W. Also speichert das zusätzliche Attribut immer die zuletzt gesehene Kante.
Statement:
Betrachte ein Algorithmus welcher ein kürzesten (s,v) Path für jeden Knoten v ∈ V liefert, dabei sind die die Distanzen von s eine real Nummer (weder -inf noch +inf).
Bei Terminierung gelten folgende Statements:
- Die incoming Kante von s ist void genau dann wenn s nicht auf einem negative cycle Paht liegt. (Das ist auch so, selbst wenn s auf einem positive cycle Path liegt. Weil der kürzeste Weg von s nach t geht nicht nochmal über s.)
- Die gespeicherten Kanten in dem zusätzlichen Attribut bilden ein cycle genau dann wenn die erreichten Knoten einen negativen Cycle bilden. (Einen positiven cycle bilden die Knoten ja nicht, das wissen wir bereits.)
Jeder cycle in diesen ausgewählten Kanten ist ein negative cycle. (Weil es positive Cycle ja nicht gibt) - Wenn die erreichten Knoten von s aus keinen negativen cycle enthält (Und positive cycle haben wir ja nicht), dann bilden die gewählten Kanten eine arborescene bei der der Knoten s die Wurzel ist und die arborescene spannt über alle erreichten Knoten.
Für jeden erreichbaren Knoten v ∈ V, der Path von s zu v in dieser Arborescene ist ein kürzester (s,v)-Path. (Ja was sonst wenn man einen shortest-path Algo laufen lässt.)
(Was ist das Problem mit negativne cycle bei andern Algos? Die Terminieren nicht?)
Beweis:
Der Algorithmus liefert d(s) < 0 genau dann wenn s auf einem negativen cycle ist. (Positive cycle gibts ja nicht und sonst ist d(s) > 0). Genau in diesem Fall wird die incoming Kante von s geupdated.
Das Beweis Statement Satz 1. (Zur Erinnerung: Satz 1: Die incoming Kante von s ist void wenn NICHT negative cycle. Wenn nicht dann void.)
(Aber woher wissen wir, dass der Algo das denn auch wirklich tut?)
Für den 2. Satz beachte erst, dass der zweite Satz impliziert den only-if Teil von dem ersten Satz, so müssen wir nicht den only-if Teil von dem ersten Satz beachten.
Sei v ein erreichbarer Knoten auf einen negative cycle. Sei p ein Path auf ausgewählten Kanten welcher in v endet.
Im Besonderen, lass p eine maximale anzahl voN Kanten von allen möglichen dieser Pathe.
Dann p kann nicht an s starte, weil der algorithmus wird eine distanz Wert für v liefern, welcher kleiner ist als die echte Distanz.
Klar, p cann nicht an einem unreachable Knoten starten. Super Klar.
(Admissible/zulässige) node potentials
Für jeden Knoten 𝑣 ∈ 𝑉, sei h(𝑣) eine reale Nummer.
Für Kante 𝑎 = (𝑣,𝑤) ∈ 𝐴, sei 𝑙h(𝑎) := 𝑙(𝑎) - h(𝑣) + h(𝑤)
In diesem Kontext, diese Werte werden gewöhnliche node potential genannt.
Node potentials sind zulässig wenn 𝑙(𝑎) >= 0 für alle 𝑎 ∈ 𝐴. Also Kantengewicht(länge) positiv ist.
Statement:
Ein (𝑠,𝑡)-path ist kürzer als ein anderer (𝑠,𝑡)-path unter der Berücksichtigung der Kantenlängen 𝑙h, genau dann wenn die selbe Aussage auch wahr ist für die Kantenlängen 𝑙. Also die shortest path Algorithmen funktionieren auch weiterhin.
Im Besonderen, der kürzeste Path unter Berücksichtigung der Kantenlängen 𝑙h ist exakt der selbe kürzeste Path unter Beachtung der Kantenlängen 𝑙. Also die Algorithmen geben sogar das selbe Ergebnis zurück. Wir haben nichts kaputt gemacht. Nur verbesser.
Beweis:
Set 𝑠 = 𝑣1 - 𝑣2 - ... - 𝑣k = 𝑡 die Knoten auf einem (𝑠,𝑡)-path. Gemein ist dass s = 𝑣1 und t = 𝑣k
Die Länge auf diesem Path unter Berücksichtigung von 𝑙h ist dann *einsetzen und umformen von 𝑙h und 𝑙 *
Also: Die Länge von einem (𝑠,𝑡)-path unter Berücksichtigung von 𝑙h und 𝑙, unterscheidet sich nur durch eine Konstante h(𝑡) - h(𝑠).
Ist ja auch klar: Wenn für jede Kante h(𝑣) subtrahiert und h(𝑤) addiert wird, und bei der nächsten Kante im Path w mit dem nächsten v tauscht. Dann heben sich die Termen in dieser Summe bis auf den ersten und letzten auf.
Anmerkung:
Admissible/zulässige node potential ermöglichen effiziente Algorithmen wie Dijkstra, welche nicht-negative Kanten Längen erwarten. Durch die node potentials kann man negative Kanten Längen ins positive ziehen.
G
𝐺
V
𝑉
A
𝐴
E
𝐸
K
𝐾
a
𝑎
k
𝑘
l
𝑙
m
𝑚
n
𝑛
p
𝑝
s
𝑠
t
𝑡
u
𝑢
v
𝑣
w
𝑤
Teilemenge
⊆
phi
φ
Element von
∈