Kürzeste Wege
-
Ein Weg in einem Graphen besteht aus den Kanten, die bestimmte Knoten miteinander
verbinden.
-
In einem Graphen ist dementsprechend der kürzeste Weg zwischen zwei
Knoten
u und v, dann minimal, wenn die Summe der Werte der
zwischenliegenden Kanten minimal ist.
-
Man kann die Entfernung eines Knotens also ermitteln, indem man den Wert
einer Kante mit der bereits ermittelten Entfernung des verbundenen Knotens
addiert, wobei am Anfang nur die Entfernung des Startknotens mit 0 feststeht.
Man muß nur noch darauf achten, das die kürzeste Entfernung
von allen Kanten-Knoten-Paaren gewählt wird.
-
Nach einigen Durchläufen wird schließlich auch die Entfernung
des Zielknotens ermittelt und der Algorithmus kann sich beenden.
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
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.
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;
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