C++Guns – RoboBlog

08.06.2019

Graph - Basics of shortest paths

Filed under: Allgemein — Thomas @ 10:06

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 𝑎.

  1. 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.
  2. 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.
  3. Wenn die Länge von einem gewöhnlichen oder generalizedn Cycle negativ ist, wird dieser Cycle einen negativen cycle genannt.
  4. Für zwei Knoten 𝑠,𝑡 ∈ 𝑉, ein kürzester Path von 𝑠 nach 𝑡 ist ein (𝑠,𝑡)-path mit minimaler Länge von allen (𝑠,𝑡) Pathe.
  5. 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

Reconstruction of a shortest path from the distances

Constructing a shortest-paths arborescence or a negative cycle

(Admissible) node potentials

G
𝐺
V
𝑉
A
𝐴
E
𝐸
K
𝐾
a
𝑎
k
𝑘
l
𝑙
m
𝑚
n
𝑛
p
𝑝
s
𝑠
t
𝑡
u
𝑢
v
𝑣
w
𝑤
Teilemenge

phi
φ
Element von

No Comments

No comments yet.

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress