TỔNG ÔN
MÔN : THIẾT KẾ THUẬT TOÁN

I / Dynamic programing
a) Gán nhãn (Dijsktra) Tìm đường đi ngắn nhất trên đồ thị có trọng số không âm từ đỉnh u ( nguồn ) tới mọi đỉnh d ( đích ). Trọng số C[i,j] là trọng số từ đỉnh i tới đỉnh j .

Trước hết ta gọi nhãn của đỉnh i ( (i : 1<= i <= N ) là cặp số ( b,v ) với ý nghĩa : b là đỉnh kề ngay trước i của đường đi ngắn nhất từ u tới i , v là giá trị đường đi ngắn nhất từ u tới i . Ký hiệu i ( b,v )

+ khởi trị nhãn :
* nhãn mọi đỉnh i là : i ( 0, Max ) ( i : 1<= i <= N
* nhãn đỉnh xuất phát là : u ( u ,0 )
* Ghi nhận đỉnh x = u và kết nạp x vào tập đỉnh đã xét : ex[x] = 1

+ Trong khi x<>d ( đích ) và ( x<>0 ) thực hiện vòng lặp :
begin
* sửa nhãn các đỉnh i ( b i ,v i ) chưa kết nạp và có đường đi từ x tới i theo nguyên tắc : gỉa sử nhãn x là x (bx , v x ) , nếu bx+ C[x,i] < bi thì đỉnh i có nhãn mới là i ( x, bx+ C[x,i] )
* Chọn đỉnh i0 có nhãn nhỏ nhất trong các đỉnh chưa kết nạp vào tập đỉnh đã xét , nếu tìm được thì kết nạp i0 vào tập đỉnh đã xét , gán x = i0 . Nếu không chọn được thì x = 0
end;
+ Lần ngược theo nhãn thứ nhất để tìm đường đi
i = đ
Trong khi i<>u thực hiện vòng lặp
Begin
+ ghi lưu i vào mảng kết quả
+ i nhận giá trị nhãn thứ nhất của i
end;

uses crt;const max = 100; fi = `dijsktra.001`;type tc = array[1..max,1..max] of integer;{ cost } tb = array[1..max] of shortint; { befor } tv = array[1..max] of integer; { value } tr = array[1..max] of char; { result }
tex = array[1..max] of 0..1; { examined : da xem xet }
var c : tc;
t : tb;
v : tv;
rs : tr;
ex : tex;
n , u , d ,x : byte;

procedure docf;
var i,j : byte;
f : text; begin
fillchar(c,sizeof(c),0);
assign(f,fi);
reset(f);
readln(f,n,u,d);
while not eof(f) do
begin
readln(f,i,j,c[i,j]);
c[j,i] := c[i,j];
end;
close(f);
end;
procedure hienf;
var i,j : byte;
begin
writeln(n,` `,u,` `,d);
for i:=1 to n do
begin
for j:=1 to n do write(c[i,j]:5);
writeln;
end;
end;
procedure khoitrinhan;
var i : byte;
begin
fillchar(ex,sizeof(ex),0);
for i:=1 to n do
begin
t[i] := 0;
v[i] := maxint;
end;
t[u] := u;
v[u] := 0;
x := u;
ex[u] := 1;
end;
procedure suanhan;
var i : byte;
begin
for i:=1 to n do
if c[x,i]>0 then
if ex[i]=0 then
begin
if v[x]+c[x,i] begin
v[i] := v[x] + c[x,i];
t[i] := x;
end;
end;
end;
function chon : byte;
var i,li : byte;
min : integer