Thuật toán Bellman

[Bellman]

Có ai biết thuật toán Bellman không, mình đang cần gấp, cám ơn các bạn nhiều.

[Bellman]

Mình làm bài này như sau nhưng chỉ chạy được với đỉnh 1. Các bạn xem gíup:
program Ford_Bellman;
const vocuc=10000;
type m1=array[1..100]of integer;
m2=array[1..100,1..100]of integer;
var x,n:integer;
f:text;
truoc:m1;
a,pi:m2;

procedure nhap;
var i,j:integer;
begin
assign(f,'Bellman.inp');
reset(f);
read(f,n,x);
for i:=1 to n do
for j:=1 to n do
read(f,a[i,j]);
close(f);
end;

procedure chuyen;
var i,j:integer;

begin
for i:=1 to n do
for j:=1 to n do
begin
if a[i,j]=-1 then
a[i,j]:=vocuc;
end;
end;

procedure tim_duong;
var i,j,k:integer;
begin
chuyen;
for i:=1 to n do
for j:=1 to n do
pi[i,j]:=vocuc;
pi[1,x]:=0;
for k:=2 to n do
for i:=1 to n do
for j:=1 to n do
if pi[k,i]>pi[k-1,j]+a[j,i] then
begin
pi[k,i]:=pi[k-1,j]+a[j,i];
truoc[i]:=j;
end;
end;

procedure xuat_dinh(y:integer);
var i,j,k:integer;
dinh:m1;
begin
dinh[1]:=y;
k:=dinh[1];
i:=1;
repeat
i:=i+1;
dinh[i]:=truoc[k];
k:=dinh[i];
until k=x;
for j:=i downto 1 do
write(f,dinh[j]:3);
end;

procedure xuat;
var i,j,k:integer;
dinh:m1;
begin
assign(f,'Bellman.out');
rewrite(f);
for i:=1 to n do
if pi[n,i]<>pi[n-1,i] then
write(f,-1)
else
for i:=1 to n do
begin
write(f,pi[n,i],':');
xuat_dinh(i);
writeln(f);
end;
close(f);
end;

BEGIN
nhap;
tim_duong;
xuat;
END.


Đồ thị
7 1
0 3 -1 -1 5 -1 -1
-1 0 1 5 -1 -1 -1
-1 -1 0 -1 -1 -1 10
1 -1 7 0 -1 -1 -1
-1 -1 -1 4 0 2 -1
-1 -1 -1 3 -1 0 2
-1 -1 -1 6 -1 -1 0

[FinderDev]

lấy tên là bellman mà không biết thuật toán bellman , bạn này quái dị thiệt

[Bellman]

Hì, mình lấy tên Bellman vì chưa biết chọn tên nào, mà đang bí nên chọn vậy thôi. Bạn nào gíup mình với, mình cảm ơn nhiều.

[Rikku]

Thuật toán Ford bellman phát biểu rất đơn giản như sau:
Với đỉnh xuất phát S.Gọi d[v] là khoảng cách tứ s tới v, các giá trị khởi tạo là:
d[s]=0;
d[v]=vô cùng..

Sau dó ta tối ưu hóa các d[v] như sau : Xét mọi đỉnh u,v của đồ thị, nếu có một cặp đỉnh u,v mà d[v]>d[u]+c[u,v] thì ta đặt lại d[v]:=d[u]+c[u,v].

Chú ý 1 điều là thuật toán chỉ thường dùng nếu đồ thị chu trình âm.

Sau đây là code:

program Ford_Bellman;
const
InputFile = 'MINPATH.INP';
OutputFile = 'MINPATH.OUT';
max = 100;
maxC = 10000;
var
c: array[1..max, 1..max] of Integer;
d: array[1..max] of Integer;
Trace: array[1..max] of Integer;
n, S, F: Integer;

procedure LoadGraph;
var
i, m, u, v: Integer;
fi: Text;
begin
Assign(fi, InputFile); Reset(fi);
ReadLn(fi, n, m, S, F);

for u := 1 to n do
for v := 1 to n do
if u = v then c[u, v] := 0 else c[u, v] := maxC;
for i := 1 to m do ReadLn(fi, u, v, c[u, v]);
Close(fi);
end;

procedure Init;
var
i: Integer;
begin
for i := 1 to n do d[i] := MaxC;
d[S] := 0;
end;

procedure Ford_Bellman;
var
Stop: Boolean;
u, v, CountLoop: Integer;
begin
for CountLoop := 1 to n - 1 do
begin
Stop := True;
for u := 1 to n do
for v := 1 to n do
if d[v] > d[u] + c[u, v] then
begin
d[v] := d[u] + c[u, v];
Trace[v] := u;
Stop := False;
end;
if Stop then Break;
end;

end;

procedure PrintResult;
var
fo: Text;
begin
Assign(fo, OutputFile); Rewrite(fo);
if d[F] = maxC then
WriteLn(fo, 'Path from ', S, ' to ', F, ' not found')
else
begin
WriteLn(fo, 'Distance from ', S, ' to ', F, ': ', d[F]);
while F <> S do
begin
Write(fo, F, '<-');
F := Trace[F];
end;
WriteLn(fo, S);
end;
Close(fo);
end;

begin
LoadGraph;
Init;
Ford_Bellman;
PrintResult;
end.

[Bellman]

Cám ơn bạn đã quan tâm. Cho mình hỏi m,s,f là gì vậy. Thuật toán Bellman yêu cầu ta tìm đường đi ngắn nhất từ 1 đỉnh đến tất cả các đỉnh khác.

[Rikku]

S là đỉnh xuất phát, F là đích. f là đỉnh nào cũng được, sau khi chạy xong thì mảng d[v] đã được tối ưu hết rùi.

[Bellman]

Không biết chương trình của bạn chạy được chưa nhưng sao mình thấy program và procedure đều là Ford_Bellman thì chắc không chạy được. Nếu bạn có thể, bạn cho mình biết email để dễ gửi chương trình.

[Rikku]

Sorry , tui gõ lộn, bạn chỉ cần bỏ program đi là CHẮC CHẮN chạy được.

[Bellman]

Hu hu, chạy được nhưng đâu có đúng. Bạn thử chạy và xem Debug\watch mảng trace xem, chỉ toàn số 0. Bạn xem lại thử.

[etoile_solitaire]

Bác Rikku cho em hỏi tí, c[u,v] là cái gì ạ ?

[Bellman]

Ôi trời, c[u,v] là mảng 2 chiều của đồ thị. Sau bao tìm tòi bây giờ mình đã làm được, nhưng bài tập của mình yêu cầu lập trình thuật toán với độ phức tạp O(n*m), bình thường là O(n^3). Có bạn nào làm được không?
Còn bài này nữa ứng dụng Bellman: Cho đồ thị, tìm xem đồ thị có mạch âm không? Nếu có hãy chỉ ra.