Hallo,
der folgende Code zeigt eine Pascal Programm mit einer Prozedur zur Ermittelung von kürzesten Wegen mit Hilfe des Dijkstra Algorithmus.
Kann mir jemand sagen, wie ich den Algorithmus verändern muß, um die längsten Wege ermitteln zu können?
Mir würde auch Pseudocode helfen...
Danke
PeMoe
{ DPFEIL1.INC: Dijkstra - Algorithmus, welcher einen Pfeilnummern-, einen
Endknoten- und einen Bewertungsvektor benutzt (pn,endknoten,cbewertung).
In dist[i] wird die Entfernung jedes Knoten i zum Startknoten a eingetragen,
in pre[i] wird jeweils der Vorg„nger auf dem Weg von a nach i eingetragen.
r[i] ist wahr, wenn Knoten i "erreicht, aber noch nicht geprÂft wurde". }
procedure Dijkstra_Pfeil1( var pre,dist : Knotenfeld;
var endknoten,cbewertung : Pfeilfeld;
var pn : Knoten_Plus_1_feld;
n : word;
a : word );
var i,j : Index;
r : Boolean_Knoten_feld;
Min : word;
begin
(*-----------------------------------------------------------------------*)
{ Schritt 1 }
for i:= 1 to n do
begin
dist[i]:= unendlich;
pre[i]:= 0;
r[i]:=FALSE;
end;
dist[a]:= 0;
r[a]:= TRUE;
(*-----------------------------------------------------------------------*)
while TRUE do
begin
(*-----------------------------------------------------------------------*)
Min:= unendlich; { Schritt 2 }
for j:= 1 to n do
if ( r[j] ) AND ( dist[j] < Min ) then
begin
Min:= dist[j];
i:=j;
end; { for/ if }
if MIN = unendlich then exit;
(*-----------------------------------------------------------------------*)
for j:= pn[i] to pn[i+1]-1 do { Schritt 3 }
if ( dist[endknoten[j]] = unendlich ) OR ( r[endknoten[j]] ) then
if dist[endknoten[j]] > dist[i] + cbewertung[j] then
begin
dist[endknoten[j]]:= dist[i] + cbewertung[j];
r[endknoten[j]]:=TRUE;
pre[endknoten[j]]:= i;
end; { for/ if/ if }
r[i]:=FALSE;
(*----------------------------------------------------------------------*)
end; { while }
end; { Ende Dijkstra_Pfeil1 -------------------------------------------- }
