Kürzeste Wege

In einem bewerteten Graphen ist der Weg zwischen zwei Knoten u und v minimal, wenn die Summe der zwischenliegenden Kanten minimal ist, d.h., für u = k2,k1, ... ,kn=v muß
S n-1 Kantenwert(ki, ki+1)
i=1
minimal werden.

Ein anderer Algorithmus für Graphen, Warshalls Algorithmus zum erzeugen der Transitiven Hülle, kann auf naheliegende Weise zu einem Algorithmus verallgemeinert werden, der zu je zwei Knoten eines bewerteten Graphen die minimale Entfernung bestimmt. Statt A[x][z] = true setzt man A[x][z] = min(A[x][z], A[x][y] + A[y][z]).
Der entsprechende Algorithmus ist auch als Floyds Algorithmus bekannt. Da man sich gewöhnlich für die kürzeste Entfernung interessiert, folgt hier nun ein Algorithmus, der auf eine ähnliche Idee aufbaut, der aber den Vorteil hat zu terminieren, sobald die kürzeste Entfernung zwischen zwei bestimmten Knoten gefunden wurde.

oben weiter

.
Mathematisch:

Wir suchen also die kürzeste Verbindung zwischen zwei Knoten u und v, in einem Graphen G auf einer Menge V. Wir definieren die Menge S aller Knoten k, für welche die kürzeste Entfernung zu u bereits bekannt ist. Diese nennen wir dist(u, k). Zu Beginn des Algorithmus gilt S := {u}. In jedem Schritt erweitert der Algorithmus die Menge S um ein neues Element. Diese Element wird bestimmt durch die Auswertung aller Paare (k1, k2) mit den Eigenschaften k1ÎS, k2ÏS, und es existiert eine Kante von k1 nach k2. Wir suchen nun unter allen Paaren (k1, k2) mit den genannten Eigenschaften dasjenige, das den kleinsten Wert (Dist(u, k1) + Kantenwert(k1, k2)) liefert. Dieser Wert ist die kürzeste Entfernung von u nach k2, und wir können ein neues S bilden mit S = S + {k2}. Wir setzen diesen Prozeß solange fort bis vÎS gilt.
oben weiter

.
Algorithmus:

for i = 1 to Knotenanzahl do MinEntf[i] = 0
S = {}
while not (Zielknoten erreicht)
    MinMin = 0
    minind = 0
    for k1 = 1 to KnotenAnzahl do
        for k2 = 1 to KnotenAnzahl do
           if isInS(k1) and not isInS(k2) and (Existiert Kante von k1 nach k2) then
                tmp = Kante[k1, k2] + MinEntf[k1]
               if tmp < MinMin then
                    MinMin = tmp
                    minind = k2
               end-if
           end-if
        end-for k2
    end-for k1
    setInS(minind)
    MinEntf[minind] = MinMin
end-while
oben weiter

.
Das heißt:

Wir berechnen für jeden Knoten die minimale Entfernung zum Knoten u, bis wir die für den gesuchten Knoten v haben. Für die Entfernungsberechnung nutzen wir für jede existierende Kante die oben bereits genannte Formel A[x][z] = min(A[x][z], A[x][y] + A[y][z]), also wird die Entfernung neu gesetzt, wenn die Entfernung des vorhergehenden Knotens plus der verbindenden Kante kleiner als die bisherige ist. Daher können wir erst mit Sicherheit die minimale Entfernung eines Knotens angeben, wenn wir die Entfernungen aller Knoten kennen, die eine Kante zu dem Knoten besitzen. Wenn dies der Fall ist, kann der Knoten zu der "Menge S" hinzugefügt werden.
oben weiter

.
Beweis (mathematisch):

Wir wollen uns noch vergewissern, daß mit Hilfe der obigen Konstruktion auch tatsächlich der kürzeste Weg von u nach k2 gefunden wurde. Angenommen, es gäbe einen kürzeren Weg von u nach k2, dann sei k der letzte Zwischenknoten dieses Weges, der noch aus S ist, und k' sei sein Nachfolger. Also hat der Weg die Struktur u...kk'...k2. Da der Gesamtweg nach k2 angeblich kürzer ist, ist auch der Weg von u nach k' kürzer als der bisher gefundene Weg. Da aber die sonstigen Voraussetzungen der Konstruktion von k2 erfüllt sind, wäre das Paar (k, k') anstatt des Paares (k, k2) von dem Algorithmus ausgewählt worden, womit wir den Widerspruch herbeigeführt haben.
oben weiter

.
Beispielrealisierung (in gekürzter Fassung):

Die Implementation basiert auf diesen Definitionen.
Die Menge S wird hier durch dem Knoten zugehörige "Marken" dargestellt. Falls die Marke eine 0 enthält, ist der Knoten nicht in der Menge, ansonsten ist er enthalten. Die Entfernung eines Knoten wird im Array MinEntfs gespeichert. 
function TGraph.ShortesWay(u, v: IndexType; var Distance :Real): Boolean;
type     TMinEntfs = array[0..0] of Real;
var      MinEntfs                     :^TMinEntfs;
         DestReached                  :^Integer;
         Knoten1, Knoten2             :^Knoten;
         k1, k2i, k2, minind          :IndexType;
         MinNeu, MinMin               :Real;
begin
 ZeroKnotenMarken;         // Menge S löschen
 inc(PointItem(u).Marke);  // u in Menge S einfügen
 GetMem(MinEntfs, sizeof(Real) * FCount); //Speicher der Entfernung besorgen
 try
   FillChar(MinEntfs^, sizeof(Real) * FCount, 0); //mit Nullen füllen
   DestReached := @(PointItem(v).Marke);
   while DestReached^ = 0 do // solange Ziel nicht erreicht/v nicht in S
    begin
     MinMin := 0.0;
     minind := 1;
     for k1 := 1 to FCount do
      begin
       Knoten1 := PointItem(k1);
       if (Knoten1.KantenCount > 0) and (Knoten1.Marke <> 0) then
                          // if Kanten vorhanden und in der Menge S
        for k2i := 0 to Knoten1.KantenCount-1 do
         begin
          k2 := Knoten1.Kanten[k2i].DestKnoten;
          Knoten2 := PointItem(k2);
          if Knoten2.Marke = 0 then // if außerhalb der Menge S 
           begin
            MinNeu := MinEntfs[k1] + Knoten1.Kanten[k2i].Value; // Neue Entfernung berechnen
            if MinNeu < MinMin then         // if neue Entfernung kleiner als alte
             begin
              MinMin := MinNeu;
              minind := k2
             end; // if MinNeu < MinMin
           end; // if Knoten2.Marke = 0
         end; // if ... for k2i := 0 to Knoten1.KantenCount-1
      end; // for k1 := 1 to FCount
     if MinMin <> 0.0 then
      begin
       inc(PointItem(minind).Marke); // Knoten in Menge S einfügen 
       MinEntfs[minind] := MinMin;   // Minimalentfernung setzen
      end;
    end; // while DestReached^ = 0
   Distance := MinEntfs[EndIndex];   // Ergebnis umspeichern 
 finally
   FreeMem(MinEntfs, sizeof(Real) * FCount);
 end;
end;
oben weiter

.
Effizienzbetrachtung:

Der Aufwand für das Hinzufügen eines neuen Knotens zu S ist bei diesem Algorithmus N2, bei dieser Realisation nur knapp über N, je nach Anzahl der Kanten. Dies multipliziert sich jeweils mit der Anzahl der notwendigen Schritte S := S + {k2}. Im ungünstigsten Fall also N mal. Damit haben wir eine Laufzeitverhalten kleiner-gleich  N3, bzw. maximal knapp über N2. Der Aufwand für den angegebenen Algorithmus läßt sich in naheliegender Weise verbessern. Im vorliegenden Fall wird die innere Schleife nur knapp über N mal durchlaufen. Es brauchen nur die Paare betrachtet zu werden, die durch eine Kante verbunden sind, die aus S herausführt.
Arrayimplementation:
N2 <= Effizienz <= N3
Momentane Realisation:
(durchschn. Kantenanzahl pro Knoten) * N <= Effizienz <= (durchschn. Kantenanzahl pro Knoten) * N2
 

Optimierungsvorschläge:

Wenn man nun eine Liste bildet mit allen Paaren für die das zutrifft, dann wird der Aufwand deutlich geringer. Man muß bei Aufnahme eines Knotens in S alle von diesem wegführenden Kanten betrachten und die aus S herausführenden neu in die Liste aufnehmen. Eine Kante der Liste wird im jedem Update-Schritt ausgewählt, die jeweils einen neu hinzuzufügenden Knoten liefert. Diese muß anschließend aus der Liste entfernt werden, da sie ja nun nicht mehr aus S herausführt. Dijkstra gibt für eine Variante dieses Algorithmus eine Laufzeit von N2 an.
oben Beispiel Beispiel 2