Cho một đồ thị có hướng
gồm n đỉnh mã số từ 1..n với các cung (u, v) có
hướng đi từ đỉnh u đến đỉnh v và có chiều dài thể hiện đường đi nối từ
đỉnh u đến đỉnh v. Viết chương trình tìm mọi đường đi ngắn nhất từ một đỉnh s
cho trước tới các đỉnh còn lại của đồ thị.
Dữ liệu vào được ghi trong một
tệp văn bản tên DIJ.INP có cấu trúc như sau:
-
Dòng đầu ghi hai số tự nhiên n và s
cách nhau bởi dấu cách, trong đó n là
số lượng đỉnh của đồ thị, s là số hiệu của đỉnh xuất phát.
-
Từ dòng thứ hai ghi lần lượt độ dài
đường đi từ đỉnh i đến các đỉnh 1,
2,..., n;
i = 1..n. Giá trị 0 cho biết không có cung nối hai đỉnh tương ứng. Với mọi đỉnh i = 1..n, cung (i, i) được xem là không tồn tại và ghi chiều dài là 0. Các số cùng dòng cách nhau qua dấu cách. Dạng dữ liệu cho như vậy được gọi là ma trận kề của đồ thị.
i = 1..n. Giá trị 0 cho biết không có cung nối hai đỉnh tương ứng. Với mọi đỉnh i = 1..n, cung (i, i) được xem là không tồn tại và ghi chiều dài là 0. Các số cùng dòng cách nhau qua dấu cách. Dạng dữ liệu cho như vậy được gọi là ma trận kề của đồ thị.
Thí dụ sau
đây cho biết đồ thị có bảy đỉnh, cần tìm các đường đi ngắn nhất từ đỉnh 2 tới
các đỉnh còn lại của đồ thị. Cung (2, 1) có chiều dài 4,...
 |
|
DIJ.INP
|
|
7 2
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
|
Dữ liệu ra được ghi trong tệp văn bản DIJ.OUT gồm n
dòng. Thông tin về mỗi đường đi ngắn
nhất từ đỉnh s đến các đỉnh còn lại
được ghi trên 1 dòng. Số đầu tiên của dòng là chiều dài đường đi. Nếu không tồn
tại đường đi thì ghi giá trị 0. Tiếp đến, trong trường hợp có đường đi từ đỉnh s đến đỉnh i thì ghi dãy đỉnh xuất hiện lần lượt trên đường đi, đỉnh đầu
tiên, dĩ nhiên là s, đỉnh cuối cùng là i.
Đường đi từ đỉnh i tới chính đỉnh đó
được coi là không tồn tại, i = 1..n. Thí dụ trên cho ta kết quả
|
DIJ.OUT
|
|
4 2 1
0
1 2 3
3 2 3 7 4
0
5 2 3 7 4 6
2
2 3 7
|
-
Đường ngắn nhất từ đỉnh 2 đến đỉnh 1 có chiều dài 4, cách đi: 2 ® 1.
-
Đường ngắn nhất từ đỉnh 2 đến đỉnh 2: không có (thực ra, theo lẽ thường
là có đường chiều dài 0).
-
Đường ngắn nhất từ đỉnh 2 đến đỉnh 3 có chiều dài 1, cách đi: 2 ® 3.
-
Đường ngắn nhất từ đỉnh 2 đến đỉnh 4 có chiều dài 3, cách
đi: 2 ® 3 ® 7 ® 4.
-
Đường ngắn nhất từ đỉnh 2 đến đỉnh 5: không có.
-
Đường ngắn nhất từ đỉnh 2 đến đỉnh 6 có chiều dài 5, cách đi: 2®3®7®4®6.
-
Đường ngắn nhất từ đỉnh 2 đến đỉnh 7 có chiều dài 2, cách đi:
2®3®7.
Bài giải
Thuật giải quy hoạch động được trình bày dưới đây mang tên Dijkstra, một nhà
tin học lỗi lạc
người Hà Lan. Bản chất của thuật toán là sửa đỉnh, chính xác ra là sửa trọng số của mỗi đỉnh.
Theo sơ đồ giải các bài toán quy hoạch động trước hết ta xây dựng hệ thức cho bài toán.
Gọi p(i) là độ dài đường ngắn nhất từ đỉnh s đến đỉnh i, 1 £ i £ n. Ta thấy, hàm p(i) phải thoả các tính chất sau:
a) p(s) = 0: đường
ngắn nhất từ đỉnh xuất phát s đến chính đỉnh đó có chiều dài 0.
b) Với i ¹ s, muốn đến được đỉnh i ta phải đến được một trong các đỉnh sát trước đỉnh i. Nếu j là một đỉnh sát trước đỉnh i, theo điều kiện của đầu
bài ta phải có
a[j,i ] > 0
trong đó a[j, i] chính là chiều dài cung (j ® i).
Trong số các đỉnh j sát trước đỉnh i ta cần chọn đỉnh nào?
Kí hiệu path(x, y) là đường đi ngắn nhất qua các đỉnh, xuất phát từ đỉnh từ x và kết thúc tại đỉnh y ¹ x. Khi đó đường từ s đến i sẽ được chia làm hai đoạn, đường
từ s đến j và cung (j ®
i):
path(s,i) = path(s,j)+ path(j,i)
trong đó path(j, i) chỉ gồm một cung:
path(j,i) = (j ® i)
Do p(i) và p(j) phải là ngắn nhất, tức là phải đạt các trị min, ta suy ra điều kiện để chọn đỉnh j sát trước đỉnh i là tổng
chiều dài đường từ s đến j và chiều dài cung (j ® i) là ngắn nhất. Ta thu được hệ thức sau:
p(i) = min
{p(j)+a[j,i ] | a[j,i ] > 0, j = 1..n }
Để ý rằng điều kiện a[j, i] > 0 cho biết j là đỉnh sát trước đỉnh i.
Điều tài tình là Dijkstra đã cung cấp thuật toán tính đồng thời mọi đường đi ngắn nhất từ đỉnh s đến các đỉnh còn
lại của đồ thị. Thuật toán đó như sau.
Thuật toán thực hiện n lần lặp, mỗi lần lặp ta
chọn và xử lí 1 đỉnh của đồ thị. Tại lần lặp thứ k ta khảo sát phần của đồ thị gồm k đỉnh với các cung liên quan đến k đỉnh được chọn trong phần đồ thị đó. Ta
gọi phần này là đồ thị con thu được tại bước xử lý thứ k
của đồ thị ban đầu và kí hiệu là G(k). Với đồ thị này ta hoàn tất bài giải tìm mọi đường đi ngắn nhất từ đỉnh xuất phát s đến mọi đỉnh
còn lại của G(k). Chiều dài thu được ta gán cho mỗi đỉnh i như một trọng số p[i]. Ngoài ra, để chuẩn bị cho
bước tiếp theo ta đánh giá lại trọng số cho mọi đỉnh kề sau của các đỉnh trong G(k).
Khởi trị:
Gán trọng số p[i] = ¥ cho mọi đỉnh,
trừ đỉnh xuất phát s,
gán trị p[s] = 0.
Ý nghĩa của
thao tác này là khi mới đứng ở đỉnh xuất phát s của đồ thị con G(0), ta coi như chưa thăm mảnh
nào của đồ thị nên ta chưa có thông
tin về đường đi từ s đến các đỉnh còn lại của đồ thị ban đầu. Nói cách khác ta coi như chưa có đường đi từ s đến các đỉnh khác s và
do đó, độ dài đường đi từ s đến các đỉnh đó là ¥.
Giá trị ¥ được chọn trong chương trình là:
MAXWORD = 65535.
Tại bước lặp thứ k ta thực hiện các thao tác sau:
-
Trong số các đỉnh chưa xử lí, tìm đỉnh i có trọng số min.
-
Với mỗi đỉnh j chưa xử lí và kề sau với đỉnh i, ta
chỉnh lại trọng số p[j] của đỉnh đó theo tiêu chuẩn sau:
Nếu p[i]
+ a[i, j] < p[j] thì gán cho p[j] giá trị mới:
p[j]=p[i]+a[i,j]
Ý nghĩa của thao tác này là: nếu độ dài đường đi path(s, j) trong đồ thị con G(k -
1) không qua đỉnh i mà lớn hơn độ dài
đường đi mới
path(s, j) có qua đỉnh i thì cập nhật lại
theo đường mới đó.
-
Sau khi cập nhật ta cần lưu lại vết cập nhật đó bằng lệnh gán before[i] = j với ý nghĩa là, đường ngắn nhất từ đỉnh s tới đỉnh j cần đi qua đỉnh i.
-
Đánh dấu đỉnh i là đã xử lí.
Như vậy, tại mỗi bước lặp ta chỉ xử lí đúng một đỉnh i có trọng số min và đánh dấu duy nhất đỉnh đó.
(*----------------------------
Thuat toan Dijkstra
------------------------------*)
procedure Dijkstra;
var i,k,j: byte;
begin
Init;
for k := 1 to n do
begin
i := Min; { tim dinh i co trong so p[i] -> min }
d[i] := 1; {danh dau dinh i la da xu
li }
for j := 1 to n do
if d[j] = 0 then {dinh chua tham }
if a[i,j] > 0 then {co duong di i -> j }
if p[i] + a[i,j] < p[j] then
begin {sua dinh }
p[j] := p[i] + a[i,j];
before[j] := i;
end;
end;
end;
Thuật toán chứa hai vòng for lồng nhau do đó có độ phức tạp là n2.
Sau khi hoàn thành thuật toán Dijkstra ta cần gọi thủ tục Ket (kết) để ghi
lại kết quả theo yêu cầu của đầu bài như sau.
Với mỗi đỉnh i = 1..n ta cần ghi vào tệp output chiều dài đường đi từ s đến i bao gồm giá trị p[i] và các đỉnh nằm trên đường đó.
Chú ý rằng nếu p[i] nhận giá trị khởi đầu tức là MAXWORD = 65535 thì
tức là không có đường đi từ s đến i.
(*-----------------------------------------
Ket thuc thuat
toan:ghi ket qua vao tep g
------------------------------------------*)
procedure Ket;
var i: byte;
begin
assign(g,gn);
rewrite(g);
for i := 1 to n do
if (i=s) or (p[i] = MAXWORD) then
writeln(g,0)
else
begin
write(g,p[i],bl);
path(i);
writeln(g);
end;
close(g);
end;
Về ý nghĩa, mảng before chứa các con trỏ ngược từ mỗi đỉnh i đến đỉnh sát trước đỉnh i trên đường đi ngắn nhất, do đó ta phải lần ngược bằng thủ tục đệ quy path(i) để ghi vào tệp g vết của đường đi theo trật tự từ s đến i.
(*-------------------------------------
Giai trinh
duong ngan nhat tu s den i.
Ghi vao file g
--------------------------------------*)
procedure
path(i: byte);
begin
if i=0 then
exit;
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;
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.
|
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
|
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
|
before
|
|
1
|
0
|
65535
|
0
|
|
2
|
0
|
0
|
0
|
|
3
|
0
|
65535
|
0
|
|
4
|
0
|
65535
|
0
|
|
5
|
0
|
65535
|
0
|
|
6
|
0
|
65535
|
0
|
|
7
|
0
|
65535
|
0
|
Bước lặp
k = 1
i
= min = v với p[v] = 0.
Các đỉnh chưa xử lí
và kề với đỉnh v sẽ được sửa trọng số là 1, 3 và 7 (có dấu P).
Vì p[v] + a[v, 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.
Vì p[v] + a[v, 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.
Vì p[v] + a[v, 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 v.
|
Đỉnh
|
d
|
p
|
before
|
|
1P
|
0
|
65535/4
|
0/2
|
|
v
|
0/1
|
0
|
0
|
|
3P
|
0
|
65535/1
|
0/2
|
|
4
|
0
|
65535
|
0
|
|
5
|
0
|
65535
|
0
|
|
6
|
0
|
65535
|
0
|
|
7P
|
0
|
65535/5
|
0/2
|
Bước lặp k = 2
i = min = w với p[w] = 1.
Đỉnh
chưa xử lí và kề với đỉnh w sẽ được sửa trọng số là đỉnh 7.
Vì p[w] + a[w, 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 w.
|
Đỉnh
|
d
|
p
|
before
|
|
1
|
0
|
65535/4
|
0/2
|
|
k
|
0/1
|
0
|
0
|
|
w
|
0/1
|
65535/1
|
0/2
|
|
4
|
0
|
65535
|
0
|
|
5
|
0
|
65535
|
0
|
|
6
|
0
|
65535
|
0
|
|
7P
|
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
|
|
k
|
0/1
|
0
|
0
|
|
l
|
0/1
|
65535/1
|
0/2
|
|
4P
|
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
i = min = 4 với p[x] = 3.
Đỉnh
chưa xử lí và kề với đỉnh x sẽ được sửa trọng số là đỉnh 6.
Vì p[x] + a[x, 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 x.
|
Đỉnh
|
d
|
p
|
before
|
|
1
|
0
|
65535/4
|
0/2
|
|
k
|
0/1
|
0
|
0
|
|
l
|
0/1
|
65535/1
|
0/2
|
|
x
|
0/1
|
65535/3
|
0/7
|
|
5
|
0
|
65535
|
0
|
|
6P
|
0
|
65535/5
|
0/4
|
|
p
|
0/1
|
65535/5/2
|
0/2/3
|
Bước lặp k = 5
i = min = u với p[u] = 4.
Không có đỉnh chưa xử lí nào kề với đỉnh u.
|
Đỉnh
|
d
|
p
|
before
|
|
u
|
0/1
|
65535/4
|
0/2
|
|
k
|
0/1
|
0
|
0
|
|
l
|
0/1
|
65535/1
|
0/2
|
|
m
|
0/1
|
65535/3
|
0/7
|
|
5
|
0
|
65535
|
0
|
|
6
|
0
|
65535/5
|
0/4
|
|
p
|
0/1
|
65535/5/2
|
0/2/3
|
Bước lặp k = 6
i = min = z với p[z] = 5.
Không có đỉnh chưa xử lí nào kề với đỉnh z. Chú ý rằng đỉnh 7 kề với đỉnh z nhưng đỉnh 7 này đã xử lí rồi.
|
Đỉnh
|
d
|
p
|
before
|
|
j
|
0/1
|
65535/4
|
0/2
|
|
k
|
0/1
|
0
|
0
|
|
l
|
0/1
|
65535/1
|
0/2
|
|
m
|
0/1
|
65535/3
|
0/7
|
|
5
|
0
|
65535
|
0
|
|
z
|
0/1
|
65535/5
|
0/4
|
|
p
|
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.
|
Đỉ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
|
Đườ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).
Không có nhận xét nào:
Đăng nhận xét