GT toán rời rạc - Phụ lục 1

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ật toán

unit Func_DoThi;

interface
type
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;Var DuongDiTuXdenY:TypeDuongDi;Var ChiPhi:real):Boolean;
Procedure DeleteGraph(VAR G:TypeDoThi);
var G:TypeDoThi;

implementation

Function DuongDiNganNhat(G:TypeDoThi;X,Y:Integer;Var DuongDiTuXdenY: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;
begin
M:=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 begin
u:=0;
While S[u]<>0 do u:=u+1;
Min:=Dist[u];i:=u+1;
While i begin
If S[i]=0 then
If ((Min.VoCung)and(not Dist[i].VoCung))or
((Not min.VoCung)and((not Dist[i].VoCung)and(min.Gia>Dist[i].Gia))) then
begin Min:=Dist[i];u:=i;end;
i:=i+1;
end;
S[u]:=1;k:=k+1;{Dua u vao tap S}
For w:=0 to M-1 do
if S[w]=0 then
begin
If (not Dist[u].VoCung)and(not Cost[u,w].VoCung)and
((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