Giáo trình tham khảo về toán rời rạc

Unit chứa khai báo các cấu trúc dữ liệu cho đồ thị và cài đặt thủ tục tìm đường đi ngắn nhất theo thuật toán.
Nội dung trích xuất từ tài liệu:
Giáo trình tham khảo về toán rời rạc PHẦN PHỤ LỤC Phụ lục 1 Unit chứa khai báo các cấu trúc dữ liệu cho đồ thịvà cài đặt thủ tục tìm đường đi ngắn nhất theo thuậttoánunit Func_DoThi;interfacetype TypeToaDo=record x,y:integer; end; TypeChiPhi=record VoCung:boolean;//Neu VoCung=True thi co nghia la chi phi bang Vo Cung,nguoc lai thi chi phi bang Gia Gia:real; end; TypeDinh=record Ten:String; ToaDo:TypeToaDo; MucKichHoat:Byte; end; TypeDanhSachDinh=array of TypeDinh; TypeCanh=record DinhDau,DinhCuoi:Integer;//Tham chieu trong danh sach Dinh TrongSo:TypeChiphi; end; TypeDanhSachCanh=Array of TypeCanh; TypeDoThi=Record SoDinh:Integer; DSDinh:TypeDanhSachDinh; SoCanh:Integer; DSCanh:TypeDanhSachCanh; end; TypeCost=Array of Array of TypeChiPhi; TypeDist=Array of TypeChiPhi; TypeDuongDi=Array of Integer;Function DuongDiNganNhat(G:TypeDoThi;X,Y:Integer;VarDuongDiTuXdenY:TypeDuongDi;Var ChiPhi:real):Boolean;Procedure DeleteGraph(VAR G:TypeDoThi);var G:TypeDoThi; 135implementationFunction DuongDiNganNhat(G:TypeDoThi;X,Y:Integer;VarDuongDiTuXdenY:TypeDuongDi;var ChiPhi:real):Boolean;Var s:Array of byte;{S[i]=0 hoac S[i]=1}Cost:TypeCost;Dist:TypeDist;MocXich:Array of Integer;M,i,j,K,u,w:Integer;Min:TypeChiPhi;beginM:=G.SoDinh; {Thuc ra M=N, ma tran vuong kich thuoc MxM}Setlength(Cost,M,M);Setlength(Dist,M);Setlength(MocXich,M);Setlength(S,M);for i:=0 to M-1 do for j:=0 to M-1 do Cost[i,j].VoCung:=True;for k:=0 to G.SoCanh-1 do begin i:=G.DSCanh[K].DinhDau;j:=G.DSCanh[K].DinhCuoi; Cost[i,j]:=G.DSCanh[K].TrongSo; end;for i:=0 to M-1 do begin S[i]:=0;Dist[i]:=Cost[X,i];MocXich[i]:=X;end;S[X]:=1;Dist[X].VoCung:=False;Dist[X].Gia:=0;K:=2; {Dua X vao S}while k ((Dist[w].VoCung)or(Dist[w].Gia>(Dist[u].Gia+Cost[u,w].Gia))) then begin Dist[w].VoCung:=false; Dist[w].Gia:=Dist[u].Gia+Cost[u,w].Gia; MocXich[w]:=u;{Duong di ngan nhat den W thi phai di qua U} end; end; end;{Tim duong di tu X den Y}Setlength(DuongDiTuXdenY,M);If not Dist[Y].VoCung then begin DuongDiNganNhat:=true; ChiPhi:=Dist[Y].gia; {Xac dinh cac dinh phai di qua (theo day chuyen nguoc)} {k:=0;DuongDiTuXdenY[k]:=Y;k:=k+1; i:=MocXich[Y];DuongDiTuXdenY[k]:=i;} K:=0;i:=Y;DuongDiTuXdenY[k]:=i; while iX do begin i:=MocXich[i];k:=k+1;DuongDiTuXdenY[k]:=i; end; {Vi chuoi chua trong DuongDiTuXdenY la mot chuoi nguoc nen ta se dao lai} for i:=0 to (k div 2) do begin j:=DuongDiTuXdenY[i]; DuongDiTuXdenY[i]:=DuongDiTuXdenY[K-i]; DuongDiTuXdenY[K-i]:=j; end; {Dat lai kich thuoc cua mang DuongDiTuXdenY bang so dinh phai di qua} Setlength(DuongDiTuXdenY,K+1); endelse DuongDiNganNhat:=false;Setlength(Cost,0,0);Setlength(Dist,0);Setlength(MocXich,0);Setlength(S,0);end;Procedure DeleteGraph(VAR G:TypeDoThi);beginG.SoDinh:=0;G.SoCanh:=0;Setlength(G.DSDinh,0);Setlength(G.DSCanh,0);end;BEGIN 137G.SoDinh :=0;G.SoCanh:=0;END.Thiết kế giao diện cho chương trình (Form 2)Với các đối tượng được gồm:Các khai báo và cài đặt cho chương form2: 138unit Unit2;interfaceuses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Mask, Buttons, ExtCtrls,Func_Dothi,Func_Graph, Menus,IdGlobal,ImgList,Jpeg;const BanKinh=20;RMuiTen=10;type TForm2 = class(TForm) Panel1: TPanel; MaskEdit1: TMaskEdit; MaskEdit2: TMaskEdit; StaticText1: TStaticText; StaticText2: TStaticText; MainMenu1: TMainMenu; imduongdingannhat1: TMenuItem; imduongdingannhat2: TMenuItem; Caykhungbenhat1: TMenuItem; Image1: TImage; PopupMenu1: TPopupMenu; Rename1: TMenuItem; Delete1: TMenuItem; N1: TMenuItem; N2: TMenuItem; ImageList1: TImageList; File1: TMenuItem; New1: TMenuItem; Open1: TMenuItem; Save1: TMenuItem; N3: TMenuItem; Exit1: TMenuItem; ScrollBox1: TScrollBox; PaintBox1: TPaintBox; Save2: TMenuItem; N6: TMenuItem; ExportPicturefile1: TMenuItem; DeleteAll1: TMenuItem; SaveDialog1: TSaveDialog; OpenDialog1: TOpenDialog; ImageList2: TImageList; SpeedButton1: TSpeedButton; SpeedButton2: TSpeedButton; 139 ExportPicturefile2: TMenuItem; N4: TMenuItem; procedure PaintBox1DragDrop(Sender, Source: TObject; X, Y: Integer); procedure PaintBox1DragOver(Sender, Source: TObject; X, Y: Integer; Sta ...