Ich kann eine Adjazenzmatrix erstellen. Der Graph ist als Klasse definiert und der Algorithmus sieht wie folgt aus:
Code: Alles auswählen
function TGraph.Dijkstra(Startknoten : integer) : TWeg;
var Vorgaenger, Distanz: array[1..MAXKNOTEN] of integer;
Erledigt: array[1..MAXKNOTEN] of boolean;
Matrix: TAdjazenzmatrix;
AktKnoten, MinKnoten: integer;
i: integer;
function Knoten_mit_kleinster_Distanz: integer;
var i: integer;
mindistanz: integer;
begin
mindistanz:= maxEntfernung;
result:= -1;
for i:= 1 to Knotenanzahl
do if (Distanz[i] < mindistanz) and (not Erledigt[i])
then begin
result:= i;
mindistanz:= Distanz[i];
end;
end;
begin
Matrix:= Adjazenzmatrix;
for i:= 1 to Knotenanzahl
do begin
Distanz[i]:= maxEntfernung;
Vorgaenger[i]:= 0;
Erledigt[i]:= false;
end;
Distanz[Startknoten] := 0;
for i:= 1 to Knotenanzahl
do begin
MinKnoten:= Knoten_mit_kleinster_Distanz;
If MinKnoten <> -1
then begin
Erledigt[MinKnoten]:= true;
for AktKnoten:= 1 to Knotenanzahl
do if (not Erledigt[AktKnoten]) and (Distanz[MinKnoten]+Matrix[MinKnoten,AktKnoten] < Distanz[AktKnoten])
then begin
Distanz[AktKnoten]:= Distanz[MinKnoten]+Matrix[MinKnoten,AktKnoten];
Vorgaenger[AktKnoten]:= MinKnoten;
end;
end;
end;
result.Anzahl:= 0;
for i:= 1 to Knotenanzahl
do begin
if i <> Startknoten
then begin
inc(result.Anzahl);
result.Kanten[result.Anzahl].Start:= Knoten[i];
result.Kanten[result.Anzahl].Ziel:= Knoten[Vorgaenger[i]];
end;
end;
end;Code: Alles auswählen
procedure TForm1.MenuItem10Click(Sender: TObject);
var Graph: TGraph;
Weg: TWeg;
Ausgabe: String;
i: integer;
Startknoten: string;
Zahl : integer;
begin
Graph:= GetGraphFromForm;
Startknoten := InputBox('Startknoten','Von wo starten?','');
Ausgabe := '';
if Startknoten <> '' then
begin
for i := 0 to Graph.Knotenanzahl do
begin
if Memo2.Lines[i] = Startknoten then
Zahl := i;
end;
Weg := Graph.Dijkstra(i);
for i := 1 to Graph.Kantenanzahl
do Ausgabe:= Ausgabe+Weg.Kanten[i].Start+Weg.Kanten[i].Ziel+'-';
ShowMessage(Ausgabe);
end;
Graph.free;
end;
Vielen Dank im Voraus!
Alci
Verein
Links
Suche