Längste Wege mit Dijkstra Algorithmus

[pemoe]

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 -------------------------------------------- }

[Gast]

In der Annahme Du meinst die längsten Wege ohne einen Knoten mehr als einmal durchzulaufen.

Dann müsstest Du es mit einer "Traveling Salesman"-Lösung versuchen, die Dir dann nicht den kürzesten Weg durch das Netz zeigt, sondern den längsten, da meiner Meinung nach der Dijkstra-Algorithmus für Deine Problemstellung ungeeignet ist.