dijkstra.pas

Dijkstra算法

unit Dijkstra;

interface


uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

const VertexNumber=5;


type
  TForm1 = class(TForm)
    Edit1: TEdit;
    Memo1: TMemo;
    Label1: TLabel;
    Label2: TLabel;
    Edit2: TEdit;
    Label3: TLabel;
    Memo2: TMemo;
    Label4: TLabel;
    Button1: TButton;
    Label5: TLabel;
    procedure Edit1KeyDown(Sender: TObject; var Key: Word;
      Shift: TShiftState);
    procedure Edit2KeyDown(Sender: TObject; var Key: Word;
      Shift: TShiftState);
    procedure FormCreate(Sender: TObject);
    procedure Button1Click(Sender: TObject);

  private
    { Private declarations }
 
    public
    { Public declarations }
  end;

  CostMatrix=array[1..VertexNumber,1..VertexNumber]of integer;
  VertexType=record
            Distance:integer;
            BelongToFirstSet,havedone:boolean;
            end;
  VertexSetType=class
            Vertex:array[1..VertexNumber]of VertexType;
            constructor Create(SourceVertex:integer;var Cost:CostMatrix);
            destructor Destroy;
            function SelectMinimumDistance:word;
            procedure UnionToFirst(U:integer);
            procedure UpdateDistance(var Cost:CostMatrix);
            procedure List(V0:integer);
            end;
  pathway=array[1..VertexNumber]of integer;

var
  Form1: TForm1;
  VertexSet:VertexSetType;
  Cost:CostMatrix;
  Count,U,V0:integer;
  VertexNumberX,VertexNumberY:word;
  TotalPath:array[1..VertexNumber]of pathway;
  
  implementation

{$R *.dfm}

constructor VertexSetType.Create(SourceVertex:integer;var Cost:CostMatrix);
var
   i,j:integer;
begin
   for i:=1 to VertexNumber do
   begin
      Vertex[i].BelongToFirstSet:=False;
      Vertex[i].Distance:=Cost[SourceVertex,i];
      Vertex[i].havedone:=false;
   end;
   Vertex[SourceVertex].BelongToFirstSet:=true;
   Vertex[SourceVertex].Distance:=0;
    for i:=1 to VertexNumber do
   begin  for j:=1 to VertexNumber do
   Totalpath[i][j]:=-1;
   end;
end;

destructor VertexSetType.Destroy;
begin
end;

function VertexSetType.SelectMinimumDistance:word;
var
   Minimum:integer;
   i,j:1..VertexNumber;
begin
   j:=1;
   while Vertex[j].BelongToFirstSet and (j<VertexNumber)do j:=j+1;
   Minimum:=Vertex[j].Distance;
   for i:=1 to VertexNumber do
   if not Vertex[i].BelongToFirstSet and(Vertex[i].Distance<Minimum)then
   begin
      Minimum:=Vertex[i].Distance;
      j:=i;
   end;
   SelectMinimumDistance:=j;
end;

procedure VertexSetType.UnionToFirst(U:integer);
begin
   Vertex[U].BelongToFirstSet:=true
end;

procedure VertexSetType.UpdateDistance(var Cost:CostMatrix);
var
   W,i:1..VertexNumber;
begin
   i:=1;
   for W:=1 to VertexNumber do
   if not Vertex[W].BelongToFirstSet and
     ((Vertex[W].Distance>Vertex[U].Distance+Cost[U,W]) or (Vertex[W].Distance=1000))then begin
     Vertex[W].Distance:=Vertex[U].Distance+Cost[U,W];
     Vertex[W].havedone:=true;
     if W<>V0 then begin
     if Vertex[U].havedone then begin
      while Totalpath[U][i]<>-1 do begin Totalpath[W][i]:=Totalpath[U][i];i:=i+1;
      end;
      Totalpath[W][i]:=U;
      i:=i+1;
      end else
     Totalpath[W][i]:=U;
     i:=i+1;
   end;
end;
end;

procedure VertexSetType.List(V0:integer);
var i:1..VertexNumber;
begin
for i:=1 to VertexNumber do
 if i<>V0 then form1.Memo2.Text:=form1.Memo2.Text+inttostr(V0)+'-->'+inttostr(i)+'==='+inttostr(Vertex[i].Distance)+'     ';
end;



procedure TForm1.Edit1KeyDown(Sender: TObject; var Key: Word;
  Shift: TShiftState);
begin
if (Key=VK_RETURN) then
 if(Edit1.Text<>'')then V0:=strtoint(Edit1.Text);
end;

procedure TForm1.Edit2KeyDown(Sender: TObject; var Key: Word;
  Shift: TShiftState);
var s:string;
begin
if (Key=VK_RETURN) then
begin
if Edit2.Text<>'' then
begin
   if VertexNumberY<>(VertexNumber+1) then
       begin
         Cost[VertexNumberX,VertexNumberY]:=strtoint(Edit2.Text);
         Edit2.Text:='';
         Memo1.Text:=Memo1.Text+inttostr(Cost[VertexNumberX,VertexNumberY])+'  ';
         VertexNumberY:=VertexNumberY+1;
       end else
       begin
       s:='';
       memo1.Lines.Add(s);
       VertexNumberY:=1;
       VertexNumberX:=VertexNumberX+1;
       Cost[VertexNumberX,VertexNumberY]:=strtoint(Edit2.Text);
         Edit2.Text:='';
         Memo1.Text:=Memo1.Text+inttostr(Cost[VertexNumberX,VertexNumberY])+'  ';
         VertexNumberY:=VertexNumberY+1;
       end;
end;
end;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
VertexNumberX:=1;
VertexNumberY:=1;
end;

procedure TForm1.Button1Click(Sender: TObject);
var i,j:integer;s:string;
begin
s:='';
VertexSet:=VertexSetType.Create(V0,Cost);
Count:=2;
while Count<VertexNumber do
begin
   U:=VertexSet.SelectMinimumDistance;
   VertexSet.UnionToFirst(U);
   Count:=Count+1;
   VertexSet.UpdateDistance(Cost);
end;
VertexSet.List(V0);
 for i:=1 to VertexNumber do begin
 memo2.Text:=memo2.Text+inttostr(V0);
  for j:=1 to VertexNumber do
  if(Totalpath[i][j]<>-1)then
        form1.Memo2.Text:=form1.Memo2.Text+'-->'+inttostr(Totalpath[i][j]);
 memo2.Text:=memo2.Text+'-->'+inttostr(i);
 memo2.Lines.Add(s);
   end;
end;


end.