Previous Contents Next

11   K"urzeste Pfade

Literatur: Teile von Kapitel 25/26 aus [CLR90]. [Ski97]
Inhalt Einleitung Varianten Relaxation Dijkstras Algorithmus Bellman-Ford lineare Programmierung
Einleitung
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:
w(p) =
k
i=1
w(vi-1, vi).
Das Gewicht des k"urzesten Pfades von u nach v ist das Minimum:
d(u,v) =



min{w(p) | u
p
 
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).

Problemvarianten
K"urzeste Pfade
K"urzeste Pfade (2)


Hauptidee: Der k"urzeste Pfad zwischen zwei Knoten
enth"alt k"urzeste Pfade als Teile
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.
Relaxation
generische Relaxation
Dijkstra


Dijkstra (2)




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
  



Bellmann-Ford
Bellmann-Ford (2)






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;





Lineare Programmierung


Darstellung als Graphproblem


January 23, 2001
Previous Contents Next