dijkstra.~pas

运筹学算法与编程实践附书源码

unit Dijkstra;

interface

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

type
  TForm1 = class(TForm)
    Panel1: TPanel;
    CheckBox1: TCheckBox;
    Edit1: TEdit;
    CheckBox2: TCheckBox;
    Panel2: TPanel;
    Label1: TLabel;
    BitBtn1: TBitBtn;
    BitBtn3: TBitBtn;
    Label2: TLabel;
    BitBtn2: TBitBtn;
    Label3: TLabel;
    Label4: TLabel;
    Label5: TLabel;
    Label6: TLabel;
    Label7: TLabel;
    Label8: TLabel;
    procedure CheckBox1Click(Sender: TObject);
    procedure CheckBox2Click(Sender: TObject);
    procedure Edit1Change(Sender: TObject);
    procedure BitBtn3Click(Sender: TObject);
    procedure BitBtn1Click(Sender: TObject);
    procedure BitBtn2Click(Sender: TObject); 
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
var CDedit2,XLmatrix,XLmatrix2,xledit2,edit2,edit,xledit:array of array of TEdit;
var HM,T,k,N,lieshu,hangshu,hangshu1,hangshu2,hangshu3,hangshu11,hangshu12,hangshu13,hangshu14:Integer;
var TGDD,C,D:array[1..999,1..999] of real;  //声明的数组类型数据：二维数组
var ZDH,QSH,B1,B2:array[1..999] of Integer;  //声明的数组类型数据：
var CDDD,B3,NC:array[1..999] of real;
implementation

{$R *.dfm}

procedure TForm1.CheckBox1Click(Sender: TObject);
begin
  CheckBox2.Checked:=CheckBox1.Checked=False;
end;

procedure TForm1.CheckBox2Click(Sender: TObject);
begin
  CheckBox1.Checked:=CheckBox2.Checked=False;
end;

procedure TForm1.Edit1Change(Sender: TObject);
begin
  N:=strtoint(Edit1.Text);
end;

procedure TForm1.BitBtn3Click(Sender: TObject);
begin
  close;
end;

procedure TForm1.BitBtn1Click(Sender: TObject);
var  i,j:inTEger;
begin
  Label4.Caption:='行点号';
  Label3.Caption:='列点号';
  //创建节点名称输入编辑框
  if edit<>nil then
    for i:=0 to hangshu1-1 do
      for j:=0 to 0 do
        edit[i,j].Free;
  hangshu1:=StrToInt(Edit1.TExt);
  SETLength(edit,hangshu1);
  for i:=low(edit) to high(edit) do
    SETLength(edit[i],1);
  for i:=low(edit) to high(edit) do
     for j:=0 to 0 do
       begin
         edit[i,j]:=TEdit.CreaTE(SElf);
         with edit[i,j] do
           begin
              Parent:=Panel2;
              Width:=40;
              Height:=25;
              left:=40+j*35;
              top:=95+i*30;
           end;
       end;
  //创建相邻节点名称显示编辑框
  if XLedit<>nil then
    for i:=0 to 0 do
      for j:=0 to hangshu2-1 do
        XLedit[i,j].Free;
  hangshu2:=StrToInt(Edit1.TExt);
  SETLength(XLedit,hangshu2);
  for i:=low(XLedit) to high(XLedit) do
    SETLength(XLedit[i],hangshu2);
  for i:=0 to 0 do
     for j:=low(XLedit) to high(XLedit) do
       begin
         XLedit[i,j]:=TEdit.CreaTE(SElf);
         with XLedit[i,j] do
           begin
              Parent:=Panel2;
              Width:=40;
              Height:=25;
              left:=110+j*45;
              top:=45+i*40;
           end;
       end;
  //创建相邻相邻矩阵参数输入编辑框
  if XLmatrix<>nil then
    for i:=0 to hangshu3-1 do
      for j:=0 to hangshu3-1 do
        XLmatrix[i,j].Free;
  hangshu3:=StrToInt(Edit1.TExt);
  SETLength(XLmatrix,hangshu3);
  for i:=low(XLmatrix) to high(XLmatrix) do
    SETLength(XLmatrix[i],hangshu3);
  for i:=low(XLmatrix) to high(XLmatrix) do
     for j:=low(XLmatrix) to high(XLmatrix) do
       begin
         XLmatrix[i,j]:=TEdit.CreaTE(SElf);
         with XLmatrix[i,j] do
           begin
              Parent:=Panel2;
              Width:=40;
              Height:=25;
              left:=110+j*45;
              top:=95+i*30;
           end;
       end;
end;

procedure TForm1.BitBtn2Click(Sender: TObject);
var NN,kK,LG,LS,LE,DD,j1,k,IQ,n,n1,i,j,x,y,flag:integer;
var P,G,W,U,V,xx:real;
label 1;
label 2;
label 3;
label 4;
label 5;
begin

  n:=StrToInt(Edit1.Text);
  lieshu:=n*(n-1);
  label5.Left:= 325+N*45;
  label5.Top:=45;
  label6.Left:= 265+N*45;
  label6.Top:= 45;
  label7.Left:=198+N*45;
  label7.Top:=45;
  label8.Left:=138+N*45;
  label8.Top:=45;

  //创建起始节点名称输出编辑框
  if edit2<>nil then
    for i:=0 to hangshu11-1 do
      for j:=0 to 0 do
        edit2[i,j].Free;
  hangshu11:=lieshu;
  SETLength(edit2,hangshu11);
  for i:=low(edit2) to high(edit2) do
    SETLength(edit2[i],1);
  for i:=low(edit2) to high(edit2) do
     for j:=0 to 0 do
       begin
         edit2[i,j]:=TEdit.CreaTE(SElf);
         with edit2[i,j] do
           begin
              Parent:=Panel2;
              Width:=40;
              Height:=25;
              left:=140+N*45+j*45;
              top:=70+i*25;
           end;
       end;
//创建终止节点名称输出编辑框
  if XLedit2<>nil then
    for i:=0 to hangshu12-1 do
      for j:=0 to 0 do
        XLedit2[i,j].Free;
  hangshu12:=lieshu;
  SETLength(XLedit2,hangshu12);
  for i:=low(XLedit2) to high(XLedit2) do
    SETLength(XLedit2[i],hangshu12);
  for i:=low(XLedit2) to high(XLedit2) do
     for j:=0 to 0 do
       begin
         XLedit2[i,j]:=TEdit.CreaTE(SElf);
         with XLedit2[i,j] do
           begin
              Parent:=Panel2;
              Width:=40;
              Height:=25;
              left:=200+N*45+j*45;
              top:=70+i*25;
           end;
       end;

  //创建最短路径值输出编辑框
  if CDedit2<>nil then
    for i:=0 to hangshu14-1 do
      for j:=0 to 0 do
        CDedit2[i,j].Free;
  hangshu14:=lieshu;
  SETLength(CDedit2,hangshu14);
  for i:=low(CDedit2) to high(CDedit2) do
    SETLength(CDedit2[i],hangshu14);
  for i:=low(CDedit2) to high(CDedit2) do
     for j:=0 to 0 do
       begin
         CDedit2[i,j]:=TEdit.CreaTE(SElf);
         with CDedit2[i,j] do
           begin
              Parent:=Panel2;
              Width:=40;
              Height:=25;
              left:=260+N*45+j*45;
              top:=70+i*25;
           end;
       end;

  //创建最短路径节点号输出编辑框
  if XLmatrix2<>nil then
    for i:=0 to hangshu13-1 do
      for j:=0 to n-1 do
        XLmatrix2[i,j].Free;
  hangshu13:=lieshu;
  SETLength(XLmatrix2,hangshu13);
  for i:=low(XLmatrix2) to high(XLmatrix2) do
    SETLength(XLmatrix2[i],n);
  for i:=low(XLmatrix2) to high(XLmatrix2) do
     for j:=low(XLmatrix2) to n-1 do
       begin
         XLmatrix2[i,j]:=TEdit.CreaTE(SElf);
         with XLmatrix2[i,j] do
           begin
              Parent:=Panel2;
              Width:=35;
              Height:=25;
              left:=320+N*45+j*35;
              top:=70+i*25;
           end;
       end;
  if checkbox1.Checked then flag:=1
  else flag:=0;
  for i:=0 to n-1 do
    for j:=0 to n-1 do
        if XLmatrix[i,j].Text='' then D[i+1,j+1]:=0
          else if (XLmatrix[i,j].Text='m')or (XLmatrix[i,j].Text='M')
              then D[i+1,j+1]:=1000000
                else  D[i+1,j+1]:=StrToFloat(XLmatrix[i,j].Text);

  HM:=1;
  for x:=1 to n do
   begin
    for y:=1 to n do
      begin
        if y<>x then
          begin
            LS:=x;
            LE:=y;
            DD:=999; //号码最多了不可能大于 999
            P:=0;
            if flag=1 then
              begin
                N1:=n-1;
                for i:=1 to n1 do
                  begin
                    j1:=i+1;
                    for j:=j1 to n do
                      begin
                        D[i,j]:=D[j,i];
                      end;
                  end;
              end;
            for i:=1 to n do
              begin
                NC[i]:=0;
                B1[i]:=0;
                B2[i]:=0;
                B3[i]:=DD;
              end;
            B1[LS]:=1;
            B3[LS]:=0;
            j:=LS;
3:          G:=DD;
            LG:=0;
            i:=1;
            while i<n+1 do
              begin
                if B1[I]=1 then  goto 1;
                U:=B3[i];
                v:=B3[j]+D[j,i];
                if U<V then W:=u
                else W:=V;
                B3[i]:=W;
                if w>=DD then goto 1;
                if u>V then b2[i]:=j;
                if w>=G then goto 1;
                LG:=I;
                G:=W;
1:              i:=i+1;
              end;
            if LG=0  then goto 2;
            B1[lg]:=1;
            j:=LG;
            if B1[LE]=0 then goto 3;
            kK:=1;
            P:=B3[LE];
            NC[N]:=LE;
            J:=LE;
4:          NN:=N-KK;
            NC[NN]:=B2[J];
            j:=B2[J];
            KK:=KK+1;
            if j<>LS then goto 4;
2:          QSH[HM]:=X;
            ZDH[HM]:=y;
            CDDD[HM]:=P;
            for j:=1 to n do
              TGDD[HM,j]:=NC[j];
            HM:=HM+1;
          end;
      end;
   end;

//输出内容
  for i:=0 to n-1 do
    XLedit[0,i].Text:=edit[i,0].Text;
  for i:=0 to lieshu-1 do
    begin
      edit2[i,0].Text:=IntToStr(QSH[i+1]);
      XLedit2[i,0].Text:=IntToStr(ZDH[i+1]);
      CDedit2[i,0].Text:=FloatToStr(CDDD[i+1]);
      for j:=0 to n-1 do
        XLmatrix2[i,j].Text:=FloatToStr(TGDD[i+1,j+1]) ;
    end;
  label5.Caption:='通过路径的顶点号码';
  label6.Caption:='长度';
  label7.Caption:='终止点';
  label8.Caption:='起始点';
end;


end.