11 K"urzeste Pfade
Literatur:
Teile von Kapitel 25/26 aus [CLR90].
[Ski97]
Inhalt
Einleitung ·Varianten ·Relaxation ·Dijkstras
Algorithmus ·Bellman-Ford ·lineare Programmierung
-
Motivation: Routing, Streckenplanung
- klass. Beispiel f"ur ein (gutartiges)
Optimierungsproblem
- gegeben: gerichteter Graph mit Gewichtungsfunktion w:
E ® R
- Problem: finde einen Verbindung/Pfad mit
minimalen Kosten
K"urzeste Pfade: Definition
|
Definition 11 [K"urzester Pfad]
Gegeben G = (V, E) gerichteter Pfad, w : E ® R. Das
Gewicht eines Pfades p = (v0, v1, ..., vk) ist
definiert:
Das Gewicht des k"urzesten Pfades von u nach v ist das
Minimum:
d(u,v) =
|
ì ï í ï î |
|
|
falls $ Pfad von u nach v |
¥ |
sonst |
|
|
Ein k"urzester Pfad von u nach v ist ein Pfad von
u nach v mit w(p) = d(u,v).
-
spezifizierte Quelle (single-source): finde
einen k"urzesten Pfad von einem gegeben Knoten f"ur jeden Zielknoten
- spezifiziertes Ziel: (single-destination):
duales Problem
- spezifizierte Quelle und Ziel (single-pair)
- k"urzeste Pfade f"ur alle Knotenpaare.
-
Hier: single-source
- Eingabe: Gerichteter Graph G = (V,E) + Quelle s Î V.
- Ausgabe: nicht nur minimales Gewicht, sondern
auch Pfad
- Þ Baum k"urzester Pfade bei gegebenem
Startknoten s:18 G' = (V',
E') mit:
-
V' Í V: Menge der von s aus erreichbaren
Knoten
- G': bewurzelter Baum mit Wurzel s
- der (eindeutige, einfache) Pfad von s nach v in V' ist ein
k"urzester Pfad von s nach v in G.
- Repr"asentierung: Im Lauf des Graphtraversierung: merke
den Vorg"anger p f"ur jeden Knoten Þ Gp =
(Vp, Ep).19
- Problem: Kanten mit negativen Kosten, insbesondere
Zyklen mit negativen Kosten.
Hauptidee:
Der k"urzeste Pfad zwischen zwei Knoten
enth"alt k"urzeste Pfade als Teile
-
Þ gutartiges Problem, viele Techniken anwendbar
-
greedy
- Relaxation
- dynamische Programmierung....
Lemma 7
geg G = (V, E), gerichtet, gewichtet mit w: E ® R.
(v1,..., vn) ist ein k"urzester Pfad von v1 nach vn und w =
(vi,..., vj) mit 1£ i £ j £ n ein Teilpfad.
Dann ist w ein k"urzester Pfad von vi nach vj.
-
Þ Zerlegung: Sei s v k"urzester Pfad mit s
u v, dann d(s,v) = d(s,u) + w(u,v).
- "`Dreiecksungleichung"'
-
d(s,v) £ d(s,u) + w(u,v) (mit (u,v) Î E)
- d(s,v) £ d(s,u) + d(u,v)
-
Methode zur Optimierung bei gutartigen Probleme
- pessimistische (worst-case) Absch"atzungen
- im Laufe des Algos immer weiter verbessert
- gutartig: ``monoton'', neue Information verbessern die
Sch"atzung nur
- f"ur k"urzeste Pfade: f"ur alle v Î V: d(v)
als obere Schranke f"ur den Pfad von s nach v.
-
generischer Relaxationsalgorithmus
-
Initialisierung: f"ur all v Î V:
-
d(v) = ¥ (au"ser s)
- d(s) = 0
- p(V) = ^
- Relaxierung einer Kante: Anwendung der
Dreiecksungleichung:
[mathescape=true,tabsize=2]
Relax(v1, v2) =
if d(v2) > d(v1) + w(v1,v2)
then p(v2) := v1;
d(v2) := d(v1) + w(v1,v2)
fi
<\code>
Unterschiedliche Algorithmen, je nachdem wann und wieoft Kanten
relaxiert werden.
-
Voraussetzung: nicht-negative Gewichtung
- S: Menge von Knoten, deren min. Gewicht bereits
bestimmt ist: d.h. v Î S Þd(v) = d(s,v)
- Hauptschritt:
Nimm den Knoten u mit der momentan geringsten
Pfadabsch"atzung aus V-S, relaxiere alle an u
adjazierenden Knoten und stecke u nach S.
- Þ Hilfsstruktur: Priority Queue
- Greedy-strategie: relaxiere immer eine Kante zu dem
unbehandelten Knoten mit dem geringsten Absch"atzung des
Abstandes.
- Graphsuche, gesteuert nach den besten Absch"atzungen, "Ahnlich
Breitensuche
- Laufzeitkomplexit"at:
-
Jeder Knoten einmal aus der Queue genommen:
O(V2)20
- jede Kante genau einmal relaxiert: O(E)
- Þ O(V2 + E) = O(V2).
Dijkstra(G,w,s)
Intitialise(G,s); // siehe generischer Algo.
S := $\emptyset$; // Knoten mit bekannter Distanz
Q := V; // priority queue
while $Q \not= \emptyset$
do
u := extract-min(Q);
S := $S \cup \{u\}$;
for all vertices $v \in Adj(u)$
do
relax(u,v)
done
done
-
beliebige Kantengewichtung, entdeckt
negativ-gewichtete Zyklen
- Relaxation der Absch"atzung des Abstandes.
- Laufzeitkomplexit"at: O(V E).
- Relaxation aller Kanten, ohne Ber"ucksichtigung ihres
Gewichtes, daf"ur gen"ugend oft (d.h. keine
greedy Strategie
Bellmann-Ford(G,w,s) // G = (V,E), Gewichtung w
initialize(G,s); // s. generischer Algo.
for i := 1 to size(V)-1
do
for all edges $(u,v) \in E$
do
relax(u,v)
done
done;
for all edges $(u,v) \in E$ // Test auf negative Zyklen
do
if d(v) > d(u) + w(u,v)
then return false
else return true
done;
-
spezielles Optimierungsproblem
- Gegeben:
-
lineare Zielfunktion +
- Menge von linearen Ungleichungen (constraints)
- Gesucht: Eingabe, soda"s Zielfunktion mit
optimaler/minimaler Wert.
- genauer:
-
gegeben
-
A x £ b
- f(x1... xn) = åi=1n c1 xi
- gesucht: minimiere f(x1... xn)
- ber"uhmtes L"osungsverfahren: Simplex-Verfahren (und
andere)
- Eingeschr"ankt hier: Differenzenungleichungen, d.h.
Ungleichungen der Form:21
xi - xj < bk
Darstellung als Graphproblem
|
-
Gegeben: Differenzenungleichungen: A x £ b.
- Definiere Constraintgraph G = (V,E) mit
-
V = {v1,... vn} (ein Extraknoten v0!)
- E = {(vi, vj)| xj - xi £ bk} È {(v1,v1),
(v0,vn)}. Die Gewichte W(vi, vj) = bk (i,j ¹0) und die
Gewichte der von v0 ausgehenden Kanten =0.
-
January 23, 2001