Bài tập phát triển dijkstra và ford-bellman, cần giúp gấp, huhu

[darkshin96]

Hjx, thầy em yêu cầu giải 1 bài thế này bằng ford-bellman và dijkstra.
Mà em chưa hiểu dc cách áp dụng 2 thuật toán này cho ma trận :((

Đề: Nhập ma trận n dòng m cột. Tìm đường đi từ bên trái ma trận (tức là A[x,1]) qua bên phải ma trận (tức là A[m,y]) sao cho tổng các số trên đường đi là lớn nhất
Từ ô A[u,v] chỉ có thể đi được qua 3 ô kế tiếp kề nó là A[u-1,v+1], A[u,v+1] và A[u+1,v+1].
Hjx, giúp em với

[HGMinh95]

Ma trận thì cũng như đồ thị thôi mà.
Coi mỗi ô trong ma trận là 1 đỉnh, có cạnh nối từ A[u,v] đến A[u-1,v+1], A[u,v+1] và A[u+1,v+1].

Mà bài này dùng QHĐ là được rồi.

[darkshin96]

hjx, bạn cho VD dc ko, tại vì ma trận kề của đồ thị thì có đường chéo A[1,1];A[2,2];A[3,3]...A[n,n] = 0 , còn ma trận này là ma trận bt T_T

[HGMinh95]

Ma trận này vs ma trận kề của đồ thị thì liên quan j` đến nhau.

Bạn nên hiểu cái ma trận đề bài cho giống như 1 bản đồ có m x n ô. Biểu diễn dưới dạng đồ thị thì nó là 1 đồ thị có hướng gồm m x n đỉnh : A[1,1] ... A[m,n], nếu từ đỉnh A[i,j] có đường đi trực tiếp đến đỉnh A[y,z] thì có cung nối từ A[i,j] -> A[y,z].

[darkshin96]

bạn cho mình xin phần code của đoạn dijkstra hoặc ford-bellman , ngồi nghiệm 1 tí dc ko ?
Hjx, rối quá

[HGMinh95]

Đây là mã giả cho ford-bellman


// Khởi tạo
for i:=1 to n do
for j:=1 to n do
d[i, j]:= + vô cùng;
d[1, 1]:= a[1,1];

// Ford-Bellman
for i:=1 to n do
for j:=1 to n do
begin
d[i-1, j+1]:= min (d[i, j] + a[i-1, j+1], d[i-1, j+1];
d[i, j+1]:= min (d[i, j] + a[i, j+1], d[i, j+1];
d[i+1, j+1]:= min (d[i, j] + a[i+1, j+1], d[i+1, j+1];
end;

[darkshin96]

Cám ơn bạn nhìu lắm ^^! Nhìu lắm lun