Autor Beitrag
Pscore
Hält's aus hier
Beiträge: 14



BeitragVerfasst: Do 30.03.06 07:04 
Habe folgendes Porblem. Dijkstra Algorithmus, ich kann zwar die Strecke des kürzesten Weges bestimmen, aber bin anscheinend zu blöd die LastNodes so zu speichern um sie zurück zu verfolgen, habe den code jetzt einmal so geändert, das bei jedem knoten alle vorgängerknoten gespeichert werden sollen. Funktioniert aber noch nicht ganz. Bitte helft mir!
Danke!
ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
Function TOptway.Optway(Start, Ziel : Word) : boolean;
var i : integer;
    CurrentNode : Word;
    SmallNode : Word;
begin
  CurrentNode := Start;
  World.Distance[CurrentNode] := 0;                    //StartNode auf 0 setzen


while (World.Distance[Ziel] > World.Distance[CurrentNode]) and (CurrentNode <> Ziel) do
  begin
  {if World.Links[CurrentNode, Ziel] then begin
                                              World.LastNode[Ziel] := inttostr(CurrentNode);
                                              Result := True;
                                              //break;
                                           end;}

    for i := 0 to World.Cityanz-1 do
    if World.Links[CurrentNode, i] = True
    then begin
           if CurrentNode <> i then
           if not World.Visited[i] then
             begin
               if World.Distance[i] = 4294967295 then
                       World.Distance[i] := Distance(CurrentNode, i) + World.Distance[CurrentNode]
               else
                  if (Distance(CurrentNode, i) + World.Distance[CurrentNode]) < World.Distance[i] then
                  World.Distance[i] := Distance(CurrentNode, i) + World.Distance[CurrentNode];
             end;
         end;
    World.Visited[CurrentNode] := true;
    SmallNode := 65535;
    For i := 0 to World.Cityanz-1 do
      if i <> Start then
      if not World.Visited[i] then
      if SmallNode = 65535 then SmallNode := i
          else if World.Distance[i] < World.Distance[SmallNode] then SmallNode := i;
    World.LastNode[SmallNode] := World.LastNode[SmallNode] + ' - ' + inttostr(SmallNode);
    CurrentNode := SmallNode;

  end;
result := true;
end;


Moderiert von user profile iconraziel: Quote- durch Delphi-Tags ersetzt
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Do 30.03.06 08:31 
Hallo,

Es waere hilfreich mehr ueber world. etc zu wissen.
Schau Dir auch mal [url=www.delphiforfun.org]DelphiForFun[/url] an und dort [url=www.delphiforfun.org...s1.htm]Graphen[/url] .
Dort wird der Loesungsweg in Pathlist gespeichert.

Gruss Horst
Pscore Threadstarter
Hält's aus hier
Beiträge: 14



BeitragVerfasst: Do 30.03.06 09:52 
Also das funktionier ja soweit nur ich kann den weg nicht ausgeben lassen, weil wenn der erst einen knoten verfolgt, speichert er immer seine schritte, wenn er dann aber feststellt, dass ein anderer knoten bisher eine kleinere distanz hat verfolgt er diesen weiter nimmt aber die schritte die er vorher gemacht hat nicht zurück, sondern speichert einfach die neuen schritte dazu. das problem ist, das ich nicht weiß wie ich die schritte löschen soll.

world ist ganz einfach aufgebaut, dort machen die funktionen nur was der name auch sagt.
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Do 06.04.06 10:46 
Hallo,

um den Weg zu finden musst Du schon zu jedem Knoten den Index des Vorgaengers speichern.
Falls Du nun zum zweiten Mal bei einem Knoten ankommst und der Weg der kuerzere ist, wird der Vorgaenger durch den neuen ersetzt.
Zum Ende laeufst Du vom Zielpunkt aus rueckwaerts ueber die jeweiligen Vorgaenger zum Startpunkt.

Gruss Horst

Zum Beispiel: A habe die Nachfolger B,C und B nur C
Von A->B->C dann steht in B A als Vorgaenger und in C eben B
Nun A->C,sei A-C < A-B-C dann wird bei C jetzt A als Vorgaenger eingetragen, was in B steht ist egal, da dieser nicht mehr erreichbar ist.