Tìm các đường ngắn nhất



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 nscá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ị.
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
Thut gii quy hoạch động được trình bày dưới đây mang tên Dijkstra, mt nhà tin hc li lc người Hà Lan. Bn cht ca thut toán là sa đỉnh, chính xác ra là sa trng s ca mi đỉnh.
Theo sơ đồ gii các bài toán quy hoch động trước hết ta xây dng h thc cho bài toán.
Gi p(i) là độ dài đường ngn nht t đỉnh s đến đỉnh i, 1 £ i £ n. Ta thy, hàm p(i) phi thoả các tính cht sau:
a) p(s) = 0: đường ngn nht t đỉnh xut phát s đến chính đỉnh đó có chiu dài 0.
b) Vi i ¹ s, mun đến được đỉnh i ta phi đến được mt trong các đỉnh sát trước đỉnh i. Nếu j là mt đỉnh sát trước đỉnh i, theo điu kin ca đầu bài ta phi 
a[j,i ] > 0
trong đó a[j, i] chính là chiu dài cung (j ® i).
Trong s các đỉnh j sát trước đỉnh i ta cn chn đỉnh nào?
Kí hiu path(x, y) là đường đi ngn nht qua các đỉnh, xut phát t đỉnh t x và kết thúc ti đỉnh y ¹ x. Khi đó đường t s đến i s được chia làm hai đon, đường t s đến j và cung (j ®i):
path(s,i) = path(s,j)+ path(j,i)
trong đó path(j, i) ch gm mt cung:
path(j,i) = (j ® i)
Do p(i) và p(j) phi là ngn nht, tc là phi đạt các tr min, ta suy ra điu kin để chn đỉnh j sát trước đỉnh i là tng chiu dài đường t s đến j và chiu dài cung (j ® i) là ngn nht. Ta thu được h thc sau:
p(i) = min {p(j)+a[j,i ] | a[j,i ] > 0, j = 1..n }
Để ý rng điu kin a[j, i] > 0 cho biết jđỉnh sát trước đỉnh i.
Điu tài tình là Dijkstra đã cung cp thut toán tính đồng thi mi đường đi ngn nht t đỉnh s đến các đỉnh còn li ca đồ th. Thut toán đó như sau.
Thut toán thc hin n ln lp, mi ln lp ta chn và x lí 1 đỉnh ca đồ th. Ti ln lp th k ta kho sát phn ca đồ th gm k đỉnh vi các cung liên quan đến k đỉnh được chn trong phn đồ th đó. Ta gi phn này là đồ th con thu được ti bước xử lý thứ  kca đồ th ban đầu và kí hiu là G(k). Vi đồ th này ta hoàn tt bài gii tìm mi đường đi ngn nht t đỉnh xut phát s đến mi đỉnh còn li ca G(k). Chiu dài thu được ta gán cho mi đỉnh i như mt trng s p[i]. Ngoài ra, để chun b cho bước tiếp theo ta đánh giá li trng s cho mi đỉnh k sau của các đỉnh trong G(k).
Khi tr: Gán trng s p[i] = ¥ cho mi đỉnh, tr đỉnh xut phát s, gán tr p[s] = 0.
Ý nghĩa ca thao tác này là khi mi đứng đỉnh xut phát s ca đồ th con G(0), ta coi như chưa thăm mnh nào ca đồ th nên ta chưa có thông tin v đường đi t s đến các đỉnh còn li ca đồ 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 chn trong chương trình là:
MAXWORD = 65535.
Ti bước lp th k ta thc hin các thao tác sau:
-          Trong s các đỉnh chưa x lí, tìm đỉnh i có trng s min.
-          Vi mi đỉnh j chưa x lí và k sau vi đỉnh i, ta chnh li trng s p[j] ca đỉnh đó theo tiêu chun sau:
Nếu p[i] + a[i, j] < p[j] thì gán cho p[j] giá tr mi:
p[j]=p[i]+a[i,j]
Ý nghĩa ca 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à ln hơn độ dài đường đi mi path(s, j) có qua đỉnh i thì cp nht li theo đường mi đó.
-          Sau khi cp nht ta cn lưu li vết cp nht đó bng lnh gán before[i] = j vi ý nghĩa là, đường ngn nht t đỉnh s ti đỉnh j cn đi qua đỉnh i.
-          Đánh du đỉnh i đã x lí.
Như vy, ti mi bước lp ta ch xđúng mt đỉnh i có trng s minđánh du duy nht đỉ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;
Thut toán cha hai vòng for lng nhau do đó có độ phc tp là n2.
Sau khi hoàn thành thut toán Dijkstra ta cn gi th tc Ket (kết) để ghi li kết qu theo yêu cu ca đầu bài như sau.
Vi mi đỉnh i = 1..n ta cn ghi vào tp output chiu dài đường đi t s đến i bao gồm giá tr p[i] và các đỉnh nm trên đường đó.
Chú ý rng nếu p[i] nhn giá tr khi đầu tc là MAXWORD = 65535 thì tc 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, mng before cha các con tr ngược t mi đỉnh i đến đỉnh sát trước đỉnh i trên đường đi ngn nht, do đó ta phi ln ngược bng th tc đệ quy path(i) để ghi vào tp g vết ca đường đi theo trt 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 ton 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 ton do
if d[i]= 0 then {dinh i chua xu li }
if p[i] <= p[m] thenm :=  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 hot động ca thut toán Dijkstra qua thí d đã cho.
Sau khi đọc d liu t tp f=DIJ.INP ta có n = 7, s = 2. Đồ th có 7 đỉnh, đỉnh xut phát là 2. Ma trn 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 lp k = 1
i = min = v vi p[v] = 0.
Các đỉnh chưa x lí và k vi đỉnh v s được sa trng s là 1, 3 và 7 (có du P).
Vì p[v] + a[v, 1] = 0 + 4 = 4 < p[1] = 65535 nên p[1] được sa thành 4 và before[1] được sa thành v.
Vì p[v] + a[v, 3] = 0 + 1 = 1 < p[3] = 65535 nên p[3] được sa thành 1 và before[3] được sa thành v.
Vì p[v] + a[v, 7] = 0 + 4 = 5 < p[7] = 65535 nên p[7] được sa thành 5 và before[7] được sa 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 vi p[w] = 1.
Đỉnh chưa x lí và k vi đỉnh w s được sa trng s  đỉnh 7.
p[w] + a[w, 7] = 1 + 1 = 2 < p[7] = 5 nên p[7] được sa thành 2 và before[7] được sa 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 vi p[{] = 1
Đỉnh chưa x lí và k vi đỉnh 7 s được sa trng s là đỉnh 4.
p[{] + a[{, 4] = 2 + 1 = 3 < p[4] = 65535 nên p[4] được sa thành 3 và before[4] được sa 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 vi p[x] = 3.
Đỉnh chưa x lí và k vi đỉnh x s được sa trng s  đỉnh 6.
p[x] + a[x, 6] = 3 + 2 = 5 < p[6] = 65535 nên p[6] được sa thành 5 và before[6] được sa 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 vi p[z] = 5.
Không có đỉnh chưa x lí nào k vi đỉnh z. Chú ý rng đỉnh 7 k vi đỉnh z nhưng đỉnh 7 này đã x lí ri.
Đỉ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
Thut toán dng.
Lưu ý rng đỉnh xut phát cho bài toán này là s = 2. Ta minh hoạ gii 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.
Để gii trình vết ca đường đi t 2 đến 4 ta da vào mng before[1..7] như sau:
Vì before[4] = 7, tc là trước khi đến đỉnh 4 phi qua đỉnh 7 nên ta có
7 ® 4
Vì before[7] = 3, tc là trước khi đến đỉnh 7 phi qua đỉnh 3 nên ta có
3 ® 7 ® 4
Vì before[3] = 2, tc là trước khi đến đỉnh 3 phi qua đỉnh 2 nên ta có
2 ® 3 ® 7 ® 4
Kết qu này được ghi ở dòng th tư ca tp DIJ.OUT như sau:
3 2 3 7 4
trong đó s đầu tiên 3 cho biết chiu dài đường đi, dãy s còn li gii trình vết ca đường đi t đỉnh 2 đến đỉnh 4.
Đường đi ngắn nhất từ đỉnh s = 2 đến đỉnh t = 5:
p[5] = 32767 ng vi giá tr dương vô cùng ¥ khi tr lúc đầu nên không có đường đi t đỉnh 2 đến đỉnh 5.
Ta ghi kết qu 0 ti dòng 5 ca tp DIJ.OUT.
Đường đi ngắn nhất từ đỉnh s = 2 đến đỉnh t = 2:
s = t nên ta coi như không có đường đi t đỉnh 2 đến đỉnh 2.
Ta ghi kết qu 0 ti dòng 5 ca tp DIJ.OUT.
Các dạng khác của bài toán Dijkstra
Lưu ý rng ma trn k có th cha các giá tr thc, tuy nhiên cn gi thiết rng mi giá tr trong ma trn k phi là các s không âm. Vi các s âm bài toán s phc tp hơn.
P1. Nếu đồ th đã cho là vô hướng ta gii như trên, ch lưu ý đến tính đối xng khi đọc d liu vào ma trn k a.
P2. Nếu đề bài ch yêu cu tìm mt đường đi t đỉnh s đến đỉnh t ta thc hin các bước sau:
1.       Đọc d liu.
2.       Gi thut toán Dijkstra.
3.       Ghi kết qu p[t] và gii trình mt đường theo thut toán path(t).

Không có nhận xét nào:

Đăng nhận xét