Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# - Tập 1 - Chương 7: Quy hoạch động

; 
Sáng tạo trong Thuật toán và Lập trình Tập I 
215 
path(before[i]); 
write(g,i,bl); 
end; 
(* Pascal *) 
(*---------------------------------------------- 
DIJ.PAS Tim cac duong ngan nhat tu mot dinh 
toi cac dinh con lai trong do thi co huong 
(thuat giai Dijkstra) 
----------------------------------------------*) 
{$B-} 
uses crt; 
const 
 MN = 100; {gioi han so dinh } 
 MAXWORD = 65535; {Gia tri duong vo cung } 
 fn = 'DIJ.INP'; 
 gn = 'DIJ.OUT'; 
 bl = #32; {dau cach } 
 nl = #13#10;{xuong dau dong moi } 
type 
 mb1 = array[0..MN] of byte; 
 mb2 = array[0..MN] of mb1; 
 mw1 = array[0..MN] of word; 
var 
 a: mb2; {ma tran ke} 
 before: mb1; {before[i] – dinh sat truoc dinh i} 
 p: mw1; {p[i] – trong so dinh i} 
 d: mb1; {d[i]=0: dinh i chua xu ly 
 d[i]=1: dinh i da xu ly} 
 n: byte; {so luong dinh} 
 s: byte; {dinh xuat phat} 
 f,g: text; 
(*--------------------------------- 
 Doc du lieu vao ma tran ke a 
-----------------------------------*) 
procedure Doc; tự viết 
(*---------------------------------------- 
Hien thi du lieu de kiem tra thu tuc doc 
-----------------------------------------*) 
procedure Xem; tự viết 
(*------------------------------------------- 
 Khoi tri 
 - trong so cac dinh: vo cung 
 - trong so dinh xuat phat s, p[s] = 0 
 - cac dinh sat truoc: 0 
--------------------------------------------*) 
procedure init; 
var i: byte; 
begin 
for i := 0 to n do 
begin 
 d[i] := 0; 
Sáng tạo trong Thuật toán và Lập trình Tập I 
216 
 p[i] := MAXWORD; 
 before[i] := 0; 
end; 
p[s] := 0; 
end; 
(*--------------------------------------- 
 Giai trinh duong ngan nhat tu s den i. 
 Ghi vao tep g 
----------------------------------------*) 
procedure path(i: byte); tự viết 
(*--------- ---------------------- 
Ket thuc thuat toan: 
ghi ket qua vao file g 
---------------------------------*) 
procedure Ket; tự viết 
(*----------------------------------- 
Trong so cac dinh chua xu ly, 
chon dinh trong so min 
-------------------------------------*) 
function Min: byte; 
var m, i: byte; 
begin 
m := 0; 
for i := 1 to n do 
if d[i]= 0 then {dinh i chua xu li } 
if p[i] <= p[m] then m := i; 
Min := m; 
end; 
(*---------------------------- 
 Thuat toan Dijkstra 
------------------------------*) 
procedure Dijkstra; tự viết 
BEGIN 
Doc; Xem; Dijkstra; ket; 
END. 
Ta minh hoạ tiến trình hoạt động của thuật toán Dijkstra qua 
thí dụ đã cho. 
Sau khi đọc dữ liệu từ tệp f=DIJ.INP ta có n = 7, s = 2. 
Đồ thị có 7 đỉnh, đỉnh xuất phát là 2. Ma trận kề a thu được 
như sau: 
Khởi trị 
Đỉnh d p befor
e 
1 0 65535 0 
2 0 0 0 
3 0 65535 0 
4 0 65535 0 
5 0 65535 0 
a 
0 0 0 0 0 0 0 
4 0 1 0 0 0 5 
0 0 0 0 0 0 1 
0 0 0 0 0 2 0 
0 0 0 3 0 0 0 
1 0 0 0 0 0 5 
0 0 0 1 0 0 0 
Sáng tạo trong Thuật toán và Lập trình Tập I 
217 
6 0 65535 0 
7 0 65535 0 
 Bước lặp k = 1 
i = min =  với p[] = 0. 
Các đỉnh chưa xử lí và kề với đỉnh  sẽ được sửa trọng số là 1, 3 và 7 (có dấu ). 
Vì p[] + a[, 1] = 0 + 4 = 4 < p[1] = 65535 nên p[1] được sửa thành 4 và 
before[1] được sửa thành . 
Vì p[] + a[, 3] = 0 + 1 = 1 < p[3] = 65535 nên p[3] được sửa thành 1 và 
before[3] được sửa thành . 
Vì p[] + a[, 7] = 0 + 4 = 5 < p[7] = 65535 nên p[7] được sửa thành 5 và 
before[7] được sửa thành . 
Đỉnh d p before 
1 0 65535/4 0/2 
 0/1 0 0 
3 0 65535/1 0/2 
4 0 65535 0 
5 0 65535 0 
6 0 65535 0 
7 0 65535/5 0/2 
Bước lặp k = 2 
i = min =  với p[] = 1. 
Đỉnh chưa xử lí và kề với đỉnh  sẽ được sửa trọng số là đỉnh 7. 
Vì p[] + a[, 7] = 1 + 1 = 2 < p[7] = 5 nên p[7] được sửa thành 2 và 
before[7] được sửa thành . 
Đỉnh d p before 
1 0 65535/4 0/2 
 0/1 0 0 
 0/1 65535/1 0/2 
4 0 65535 0 
5 0 65535 0 
6 0 65535 0 
7 0 65535/5/2 0/2/3 
Bước lặp k = 3 
i = min = 7 với p[] = 1 
Đỉnh chưa xử lí và kề với đỉnh 7 sẽ được sửa trọng số là đỉnh 4. 
Vì p[] + a[, 4] = 2 + 1 = 3 < p[4] = 65535 nên p[4] được sửa thành 3 và 
before[4] được sửa thành . 
Đỉnh d p before 
1 0 65535/4 0/2 
 0/1 0 0 
 0/1 65535/1 0/2 
4 0 65535/3 0/7 
5 0 65535 0 
6 0 65535 0 
 0/1 65535/5/2 0/2/3 
Bước lặp k = 4 
Sáng tạo trong Thuật toán và Lập trình Tập I 
218 
i = min = 4 với p[] = 3. 
Đỉnh chưa xử lí và kề với đỉnh  sẽ được sửa trọng số là đỉnh 6. 
Vì p[] + a[, 6] = 3 + 2 = 5 < p[6] = 65535 nên p[6] được sửa thành 5 và 
before[6] được sửa thành . 
Đỉnh d p before 
1 0 65535/4 0/2 
 0/1 0 0 
 0/1 65535/1 0/2 
 0/1 65535/3 0/7 
5 0 65535 0 
6 0 65535/5 0/4 
 0/1 65535/5/2 0/2/3 
Bước lặp k = 5 
i = min =  với p[] = 4. 
Không có đỉnh chưa xử lí nào kề với đỉnh . 
Đỉnh d p before 
 0/1 65535/4 0/2 
 0/1 0 0 
 0/1 65535/1 0/2 
 0/1 65535/3 0/7 
5 0 65535 0 
6 0 65535/5 0/4 
 0/1 65535/5/2 0/2/3 
Bước lặp k = 6 
i = min =  với p[] = 5. 
Không có đỉnh chưa xử lí nào kề với đỉnh . Chú ý rằng đỉnh 7 kề với đỉnh  
nhưng đỉnh 7 này đã xử lí rồi. 
Đỉnh d p before 
 0/1 65535/4 0/2 
 0/1 0 0 
 0/1 65535/1 0/2 
 0/1 65535/3 0/7 
5 0 65535 0 
 0/1 65535/5 0/4 
 0/1 65535/5/2 0/2/3 
Thuật toán dừng. 
Lưu ý rằng đỉnh xuất phát cho bài toán này là s = 2. Ta minh hoạ giải trình kết quả 
cho ba thí dụ sau. 
Sáng tạo trong Thuật toán và Lập trình Tập I 
219 
Đường đi ngắn nhất từ đỉnh s = 2 đến đỉnh t = 4: 
Vì p[4] = 3 nên độ dài đường đi là 3. 
Để giải trình vết của đường đi từ 2 đến 4 ta dựa 
vào mảng before[1..7] như sau: 
Vì before[4] = 7, tức là trước khi đến đỉnh 4 phải 
qua đỉnh 7 nên ta có 
7  4 
Vì before[7] = 3, tức là trước khi đến đỉnh 7 phải 
qua đỉnh 3 nên ta có 
3  7  4 
Vì before[3] = 2, tức là trước khi đến đỉnh 3 phải qua đỉnh 2 nên ta có 
2  3  7  4 
Kết quả này được ghi ở dòng thứ tư của tệp DIJ.OUT như sau: 
3 2 3 7 4 
trong đó số đầu tiên 3 cho biết chiều dài đường đi, dãy số còn lại giải trình vết của 
đường đi từ đỉnh 2 đến đỉnh 4. 
Đường đi ngắn nhất từ đỉnh s = 2 đến đỉnh t = 5: 
Vì p[5] = 32767 ứng với giá trị dương vô cùng  khởi trị lúc đầu nên không có 
đường đi từ đỉnh 2 đến đỉnh 5. 
Ta ghi kết quả 0 tại dòng 5 của tệp DIJ.OUT. 
Đường đi ngắn nhất từ đỉnh s = 2 đến đỉnh t = 2: 
Vì s = t nên ta coi như không có đường đi từ đỉnh 2 đến đỉnh 2. 
Ta ghi kết quả 0 tại dòng 5 của tệp DIJ.OUT. 
Các dạng khác của bài toán Dijkstra 
Lưu ý rằng ma trận kề có thể chứa các giá trị thực, tuy nhiên cần giả thiết rằng mọi 
giá trị trong ma trận kề phải là các số không âm. Với các số âm bài toán sẽ phức tạp 
hơn. 
P1. Nếu đồ thị đã cho là vô hướng ta giải như trên, chỉ lưu ý đến tính đối xứng khi 
đọc dữ liệu vào ma trận kề a. 
P2. Nếu đề bài chỉ yêu cầu tìm một đường đi từ đỉnh s đến đỉnh t ta thực hiện các 
bước sau: 
1. Đọc dữ liệu. 
2. Gọi thuật toán Dijkstra. 
3. Ghi kết quả p[t] và giải trình một đường theo thuật toán path(t). 
// C# 
using System; 
using System.IO; 
using System.Collections; 
namespace SangTaoT1 
{ 
 /*------------------------------------ 
 * Thuat toan Dijkstra 
 * Tim moi duong ngan nhat tu mot dinh 
 * den moi dinh con lai 
 * -----------------------------------*/ 
 class Dijkstra 
Đỉnh d p before 
1 1 4 2 
2 1 0 0 
3 1 1 2 
4 1 3 7 
5 0 65535 0 
6 1 5 4 
7 1 2 3 
Sáng tạo trong Thuật toán và Lập trình Tập I 
220 
 { 
 const string fn = "Dij.inp"; 
 const string gn = "Dij.out"; 
 static int n = 0; // so dinh 
 static int s = 0; // dinh xuat phat 
 // c[i,j] ma tran ke cho biet 
 // do dai cung (i,j) 
 static int[,] c; 
 static int[] d; // danh dau dinh 
 static int[] t; // tro truoc 
 static int[] p; // trong so dinh 
 static void Main() 
 { 
 Run(); 
 Console.ReadLine(); 
 } // Main 
 static void Run() 
 { 
 Doc(); Show(); Dij(); 
 Ghi(); Test(); 
 Console.WriteLine("\n Fini"); 
 Console.ReadLine(); 
 } 
 // Kiem tra lai tep output 
 static void Test() tự viết 
 static void Ghi() 
 { 
 StreamWriter g = File.CreateText(gn); 
 for (int i = 1; i <= n; ++i) 
 if (i == s || p[i] == int.MaxValue) 
 g.WriteLine(0); 
 else 
 { 
 g.Write(p[i] + " "); 
 int u = InvPath(i); 
 for (int j = u; j > 0; --j) 
 g.Write(d[j] + " "); 
 g.WriteLine(); 
 } 
 g.Close(); 
 } 
 // Lan nguoc duong di 
 // tu dinh v den dinh s 
 // ghi tam vao mang d 
 static int InvPath(int v) 
 { 
 int i = 0; 
 do 
 { 
 d[++i] = v; 
 v = t[v]; 
 } while (v != 0); 
 return i; 
Sáng tạo trong Thuật toán và Lập trình Tập I 
221 
 } 
 static void Dij() 
 { 
 for (int i = 0; i <= n; ++i) 
 { //d: danh dau dinh, t: tro truoc 
 d[i] = t[i] = 0; 
 p[i] = int.MaxValue; // Trong so 
 } 
 p[s] = 0;// s: dinh xuat phat 
 for (int i = 1; i < n; ++i) 
 { 
 int u = Minp();// u: dinh trong so min 
 d[u] = 1; // danh dau dinh da xet 
 // sua lai nhan dinh 
 for (int v = 1; v <= n; ++v) 
 if (d[v] == 0) // dinh chua xet 
 if (c[u, v] > 0) // co cung(u,v) 
 if (p[u] + c[u, v] < p[v]) 
 { // sua lai nhan dinh v 
 p[v] = p[u] + c[u, v]; 
 // chon cach di tu u -> v 
 t[v] = u; 
 } 
 } 
 } 
 // Tim trong so cac dinh chua 
 // xu li mot dinh j co p min 
 static int Minp() 
 { 
 int jmin = 0; 
 for (int i = 1; i <= n; ++i) 
 if (d[i] == 0) // dinh i chua xet 
 if (p[i] < p[jmin]) jmin = i; 
 return jmin; 
 } 
 static void Doc() 
 { 
 int[] a = Array.ConvertAll((File. 
 ReadAllText(fn)).Split( 
 new char[] {'\0','\n','\t','\r',' '}, 
 StringSplitOptions.RemoveEmptyEntries), 
 new Converter(int.Parse)); 
 n = a[0]; // so dinh 
 s = a[1]; // dinh xuat phat 
 c = new int[n + 1, n + 1]; 
 d = new int[n + 1]; 
 t = new int[n + 1]; 
 p = new int[n + 1]; 
 int k = 2; 
 for (int i = 1; i <= n; ++i) 
 for (int j = 1; j <= n; ++j) 
 c[i, j] = a[k++]; 
 } 
Sáng tạo trong Thuật toán và Lập trình Tập I 
222 
 // Hien thi du lieu 
 static void Show() tự viết 
 // hien thi mang 
 static void Print(int[] a, int n) tự viết 
 } // Dijkstra 
} // SangTao1