HỌC VIỆN KỸ THUẬT QUÂN SỰ

KHOA CÔNG NGHỆ THÔNG TIN
--------O0O--------

BÀI TẬP MÔN

PHÂN TÍCH VÀ ĐÁNH GIÁ THUẬT TOÁN

Giáo viên hướng dẫn: PGS TS Đào Thanh Tĩnh
Người thực hiện: Phạm Phương Duy
Lớp: Cao học CNTT – khóa K25

HÀ NỘI 2014


MỤC LỤC
LỜI NÓI ĐẦU..................................................................................................................................1


1

LỜI NÓI ĐẦU
Trên thực tế có nhiều bài toán liên quan tới một tập các đối tượng và những
mối liên hệ giữa chúng, đòi hỏi toán học phải đặt ra một mô hình biểu diễn một
cách chặt chẽ và tổng quát bằng ngôn ngữ ký hiệu, đó là đồ thị. Những ý tưởng cơ
bản của nó được đưa ra từ thế kỷ thứ XVIII bởi nhà toán học Thụy Sĩ Leonhard
Euler, ông đã dùng mô hình đồ thị để giải bài toán về những cây cầu Konigsberg
nổi tiếng.
Mặc dù Lý thuyết đồ thị đã được khoa học phát triển từ rất lâu nhưng lại có
nhiều ứng dụng hiện đại. Đặc biệt trong khoảng vài mươi năm trở lại đây, cùng với

sự ra đời của máy tính điện tử và sự phát triển nhanh chóng của Tin học, Lý thuyết
đồ thị càng được quan tâm đến nhiều hơn. Đặc biệt là các thuật toán trên đồ thị đã
có nhiều ứng dụng trong nhiều lĩnh vực khác nhau như: Mạng máy tính, Lý thuyết
mã, Tối ưu hóa, Kinh tế học,… Chẳng hạn như trả lời câu hỏi: Hai máy tính trong
mạng có thể liên hệ được với nhau hay không?; hay vấn đề phân biệt hai hợp chất
hóa học có cùng công thức phân tử nhưng lại khác nhau về công thức cấu tạo cũng
được giải quyết nhờ mô hình đồ thị.
Bài toán tìm hai đường đi sao cho không có cạnh nào chung và có tổng độ
dài ngắn nhất trong Lý thuyết đồ thị là bài toán có ứng dụng cao trong thực tế. Vì
vậy, em chọn đề bài này để nghiên cứu.
Cấu trúc của báo cáo được chia thành hai phần:
Phần I: Giới thiệu bài toán
Trình bày bài toán đặt ra và mô tả dữ liệu vào ra của bài toán.
Phần II: Giải quyết bài toán
Trình bày những khái niệm cơ bản liên quan đến đồ thị và thuật toán tìm
đường đi ngắn nhất Dijkstra và thuật toán tìm đường đi theo chiều sâu. Từ đó kết
hợp hai thuật toán để giải quyết bài toán đặt ra của báo cáo.


2

Để hoàn thành báo cáo này trước hết chúng em xin chân trọng tỏ lòng biết ơn
tới PGS. TS Đào Thanh Tĩnh - người đã trực tiếp giảng dạy môn học Phân tích và
Đánh giá thuật toán với cách thức truyền đạt hết sức khoa học và nghiêm túc.
Chúng tôi cũng xin chân thành cảm ơn các bạn bè và đồng nghiệp đã nhiệt tình
giúp đỡ và chỉ bảo, vì còn hạn chế về nhiều mặt nên báo cáo không tránh khỏi
những thiếu sót, rất mong được Thầy cùng các bạn nhận xét và góp ý để chúng tôi
hoàn thiện báo cáo hơn nữa.



3

Phần I
GIỚI THIỆU BÀI TOÁN
1. Bài toán đặt ra
Cho đồ thị vô hướng G ={V, E} được cho bởi danh sách cạnh DS. Cho u, v
∈ V. Xây dựng thuật toán tìm hai đường đi α (u,v) và β (u,v) sao cho không có
cạnh nào chung và có tổng độ dài ngắn nhất.
 Phát biểu lại bài toán:
- Có đồ thị vô hướng G gồm n đỉnh và m cạnh được cho bởi danh sách cạnh
như sau:
Canh = Record
d,c: Tên đỉnh;
Length: Độ dài đường đi;
End;
Ds[1..m] Of Canh;
- Yêu cầu: Tìm hai đường đi α (u,v) và β (u,v) sao cho không có cạnh nào
chung và có tổng độ dài ngắn nhất.
2. Mô tả dữ liệu vào/ra của bài toán
2.1. Dữ liệu vào
Từ file văn bản “dulieuvao.inp” có cấu trúc như sau:
+ Dòng thứ nhất ghi 4 số nguyên dương cách nhau một dấu cách lần lượt là:
- n là số đỉnh của đồ thị G;
- m là số cạnh của đồ thị G;
- u đỉnh xuất phát;
- v đỉnh đích.
+ Dòng thứ i trong số m dòng tiếp theo ghi ba số cách nhau một dấu lần lượt
là:

3



4

- d là đỉnh đầu của một cạnh;
- c là đỉnh cuối của một cạnh;
- Length là độ dài của cạnh (đường đi).
2.2. Dữ liệu ra
Được ghi vào file văn bản “dulieura.out” có cấu trúc như sau:
+ Dòng thứ nhất ghi đường đi α (u,v);
+ Dòng thứ hai ghi đường đi β (u,v);
+ Dòng thứ ba tổng độ dài ngắn nhất của hai đường đi;

4


5

Phần II
GIẢI QUYẾT BÀI TOÁN
1. Khái niệm cơ bản về đồ thị
1.1. Định nghĩa đồ thị (Graph)
Là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Được mô
tả hình thức:
G=(V,E)
V gọi là tập các đỉnh (Vertices) và E gọi là tập các cạnh (Edges). Có thể coi
E là tập các cặp (u, v) với u và v là hai đỉnh của V.
Một số hình ảnh của đồ thị:

Có thể phân loại đồ thị theo đặc tính và số lượng của tập các cạnh E:

Cho đồ thị G=(V, E). Định nghĩa một cách hình thức
1. G được gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V có nhiều nhất là 1
cạnh trong E nối từ u tới v.
2. G được gọi là đa đồ thị nếu giữa hai đỉnh u, v của V có thể có nhiều hơn 1
cạnh trong E nối từ u tới v (Hiển nhiên đơn đồ thị cũng là đa đồ thị).
3. G được gọi là đồ thị vô hướng nếu các cạnh trong E là không định hướng,
tức là cạnh nối hai đỉnh u, v bất kỳ cũng là cạnh nối hai đỉnh u, v. Hay nói cách
khác, tập E gồm các cặp (u, v) không tính thứ tự. (u, v) ≡ (v, u ) .
5


6

4. G được gọi là đồ thị có hướng nếu các cạnh trong E là có định hướng, có
thể có cạnh nối từ đỉnh u tới đỉnh v nhưng chưa chắc đã có cạnh nối từ đỉnh v tới
đỉnh u. Hay nói cách khác, tập E gồm các cặp (u, v) có tính thứ tự: (u, v) ≠ (v, u ) .
Trong đồ thị có hướng, các cạnh được gọi là các cung. Đồ thị vô hướng cũng
có thể coi là đồ thị có hướng nếu như ta coi cạnh nối hai đỉnh u, v bất kỳ tương
đương với hai cung (u, v) và (v, u).
Ví dụ:

1.2. Biểu diễn đồ thị trên máy tính
1.2.1. Ma trận kiền kề (Ma trận kề)
Giả sử G=(V, E) là một đơn đồ thị có số đỉnh (ký hiệu V ) là n. Không mất
tính tổng quát có thể coi các đỉnh được đánh số 1, 2,…, n. Khi đó ta có thể biểu

[ ]

diễn đồ thị bằng một ma trận vuông A = aij cấp n. Trong đó:
• aij = 1 nếu ( i, j ) ∈ E

• aij = 0 nếu ( i, j ) ∉ E
• Quy ước aii = 0 với ∀i ;
Đối với đa đồ thị thì việc biểu diễn cũng tương tự trên, chỉ có điều nếu như (i, j) là
cạnh thì không phải ta ghi số 1 vào vị trí aij mà là ghi số cạnh nối giữa đỉnh i và
đỉnh j.

6


7

1.2.2. Danh sách cạnh
Trong trường hợp đồ thị có n đỉnh, m cạnh, ta có theerbieeur diễn đồ thị
dưới dạng danh sách cạnh, trong cách biểu diễn này, người ta liệt kê tất cả các cạnh
của đồ thị trong một danh sách, mỗi phần tử của danh sách là một cặp (u, v) tương
ứng với một cạnh của đồ thị. (Trong trường hợp đồ thị có hướng thì mỗi cặp (u, v)
tương ứng với một cung, u là đỉnh đầu và v là đỉnh cuối của cung). Danh sách được
lưu trong bộ nhớ dưới dạng mảng hoặc danh sách móc nối. Ví dụ với đồ thị dưới
đây:

7


8

Ưu điểm của danh sách cạnh:
 Trong trường hợp đồ thị thưa (có số cạnh tương đối nhỏ: chẳng hạn m <
6n), cách biểu diễn bằng danh sách cạnh sẽ tiết kiệm được không gian lưu trữ, bởi
nó chỉ cần 2m ô nhớ để lưu danh sách cạnh.
 Trong một số trường hợp, ta phải xét tất cả các cạnh của đồ thị thì cài đặt

danh sách cạnh làm cho việc duyệt các cạnh dễ dàng hơn. (Thuật toán Kruskal
chẳng hạn).
Nhược điểm của danh sách cạnh:
 Nhược điểm cơ bản của danh sách cạnh là khi ta cần duyệt tất cả các đỉnh
kề với đỉnh v nào đó của đồ thị, thì chẳng có cách nào khác là phải duyệt tất cả các
cạnh, lọc ra những cạnh đó chứa đỉnh v và xét đỉnh còn lại. Điều đó khá tốn thời
gian trong trường hợp đồ thị dày (nhiều cạnh).
1.3. Dây chuyền, chu trình, đường đi và Mạch
Cho đồ thị G=(V,E).
Dây chuyển: Một day chuyền trong G là một dãy luân phiên các đỉnh và
cạnh: v1e1v2 e2  vm−1em−1vm ( vi là đỉnh và ei là cạnh)
Trong đồ thị thỏa mãn điều kiện ei liên kết với cặp đỉnh vi , vi +1 không phân biệt thứ
tự, nghĩa là:
ei = ( vi , vi +1 ) hay ei = ( vi +1 , vi ) nếu đồ thị có hướng,
ei = { vi , vi +1} nếu đồ thị vô hướng.
Khi đó ta gọi v1 là đỉnh đầu và vm là đỉnh cuối của dây chuyền.
Dây chuyền sơ cấp: Dây chuyền không có đỉnh lặp lại.
Chu trình: Là một dây chuyền v1e1v2 e2  vm−1em−1vm em v1 sao cho các đỉnh
v1 , v2 , , vm đôi một khác nhau.
Đường đi: Một đường đi trong G là một dãy luân phiên các đỉnh và cạnh:
v1e1v2 e2  vm−1em−1vm ( vi là đỉnh và ei là cạnh)

8


9

trong đồ thị thỏa mãn điều kiện ei liên kết với cặp đỉnh ( vi , vi +1 ) , nghĩa là:
ei liên kết với ( vi , vi +1 ) nếu đồ thị có hướng,
ei liên kết với { vi , vi +1} nếu đồ thị vô hướng.

Khi đó ta gọi v1 là đỉnh đầu và vm là đỉnh cuối của đường đi.
Đường đi sơ cấp: Đường đi không có đỉnh lặp lại.
Mạch: Là một đường đi v1e1v2 e2  vm−1em−1vm em v1 sao cho các đỉnh
v1 , v2 , , vm đôi một khác nhau.
2. Thuật toán tìm đường đi ngắn nhất Dijkstra
Xét đồ thị G=(V,E) có trọng với V = {1,2, , n} và giả sử các cạnh không âm.
- Dữ liệu nhập cho thuật toán là ma trận trọng lượng L (với qui ước
Lhk = +∞ nếu không có cạnh nối từ đỉnh h đến đỉnh k) và hai đỉnh i, j cho trước.
- Dữ liệu xuất là đường đi ngắn nhất từ i đến j.
Bước 1: Gán T:= V và gắn các nhãn:
Dodai[i]=0; Dodai[k]= + ∞ , ∀k ∈V \ { i} ;
Nhan[k]= -1, ∀k ∈V .
Bước 2: Nếu j ∉ T thì dừng và giá trị Dodai[j] chính là độ dài đường đi ngắn
nhất từ i đến j và Nha[j] là đỉnh nằm ngay trước j trên đường đi đó.
Bước 3: Chọn đỉnh v ∈ T sao cho Dodai[v] nhỏ nhất và gán T := T \ { v} .
Bước 4: Với mọi đỉnh k ∈ T và có cạnh nối từ v đến k,
nếu Dodai[k] > Dodai[v] + Lvk thì
Dodai[k] = Dodai[v] + Lvk và Nha[k] = v
Trở về bước 2.
Ghi chú: Khi thuật toán dừng, nếu Dodai[j]= + ∞ thì không tồn tại đường đi từ i
đến j, nếu ngược lại thì Dodai[j] là độ dài đường đi ngắn nhất và ta lần ngược ra
đường đi ngắn nhất (đi ngược từ j trờ về lại i) như sau:
write(j);
9


10

k:= Nhan[j];
while k<>i Do

Begin
write(‘<--‘, k);
K:= Nhan[k];
End;
write(‘<--‘, i);
Ví dụ: Áp dụng thuật toán Dijkstra, tìm đường đi ngắn nhất giữa đỉnh k đến đỉnh e,
với dữ liệu đồ thị G có hướng, liên thông được cho bởi danh sách cạnh sau:
1)
2)
3)
4)
5)
6)
7)
8)

a b 5
f e 2
g h 2
m k 2
k j 1
h i 1
i e 2
e d 1

9)
10)
11)
12)
13)

14)
15)
16)

b
a
f
g
e
g
h
k

c 2
f 6
g 6
m 6
b 3
k 5
e 4
h 4

17)
18)
19)
20)
21)
22)
23)
24)


d c 6
i d 6
j i 6
a e 1
m h 6
f b 5
e c 2
d b 5

25)
26)
27)
28)
28)

h f 5
h d 5
e g 3
j h 2
k i 5

Giải
- Từ dữ liệu về đồ thị ta có danh sách kề sau:
V-

V
a
a, e, f, d b
b, d, e c

e, i, h
d
f, i, h, a e
a, h f
f, e g
g, k, m, h
j
h, j, k i
m, g k
g m
k j

V+
b, f, e
c
c, b
d, b, c, g
e, g, b
h, m, k
i, e, f, d
e, d
j, h, i
k, h
i, h

- Ta dùng bảng dưới đây để tìm đường đi ngắn nhất từ đỉnh k đến đỉnh e:
10


11


Bước

Đỉnh
đang xét

0
1
2
3

k
j
h

4
5

i
e

Nh

a

b

c

d


e

f

g

h

i

k

m

j

S

∞
∞
∞
∞
∞

∞
∞
∞
∞
∞


∞
∞
∞
∞
∞

∞
∞
∞
∞

∞
∞
∞
∞

∞

∞
∞

∞
∞

0
0

4
3


5
5

φ
k
k, j
k, j, h

7

8

∞
∞
∞
∞
∞

∞

8

∞
∞
∞
∞
∞

∞


∞

∞

8

6

8

∞

∞
∞

∞

4

∞

∞

1

k, j, h, i
k, j, h, i,
e


Từ bảng trên ta có độ dài đường đi từ k tới e là 6. Xác định đường đi:
1) u0 = e;
2) V-(e) = {f, i, h, a} ; L(e) = 6;
L(f)= 5; F(f,e) = 2; L(f) + F(f,e) = 5 + 2 = 7 > 6 = L(e).
L(i)= 4; F(i,e) = 2; L(i) + F(i,e) = 4 + 2 = 6 = 6 = L(e).
L(h)= 3; F(h,e) = 4; L(h) + F(h,e) = 3 + 4 = 7 > 6 = L(e).
L(a)= ∞ ; F(a,e) = 1; L(a) + F(a,e) = ∞ + 1 = ∞ > 6 = L(e).
Vậy u1 = i;
2) V-(i) = {h, j, k}
L(h)= 3; F(h,i) = 1; L(h) + F(h,i) = 3 + 1 = 4 = 4 = L(i).
L(j)= 1; F(j,i) = 6; L(j) + F(j,i) = 1 + 6 = 7 > 4 = L(i).
L(k)= 0; F(k,i) = 5; L(k) + F(k,i) = 0 + 5 = 5 > 4 = L(i).
Vậy u2 = h;
3) V-(h) = {g, k, m, j}
L(g)= 9; F(g,h) = 2; L(g) + F(g,h) = 9 + 2 = 11 > 3 = L(h).
L(k)= 0; F(k,h) = 4; L(k) + F(k,h) = 0 +4 = 4 > 3 = L(h).
L(m)= ∞ ; F(m,h) = 6; L(m) + F(m,h) = ∞ + 6 = ∞ > 3 = L(h).
L(j)= 1; F(j,h) = 2; L(j) + F(j,h) = 1 + 2 = 3 = 3 = L(h).
Vậy u3 = j;
4) V-(j) = {k}
L(k)= 0; F(k,j) = 1; L(k) + F(k,j) = 0 + 1 = 1 = 1 = L(j).

11


12

Vậy u4 = k;
Suy ra đường đi từ k tới e là: <k, j, h, i, e>
3. Thuật toán duyệt các đỉnh của đồ thị theo theo chiều sâu

+ Input: - Đồ thị G liên thông, có n đỉnh, được cho bởi ma trận kề A=(aij)n.
+ Output: - Các đỉnh của đồ thị
+ Giả mã:
1. For i:= 1 To n Do Đx[i]:= False;
2. Procedure DS(v: Đỉnh xuất phát);
Đx[v]:= True;
Output v;
For i:=1 To n Do
If (!Đx[i]) and (A[v,i]=1) Then DS(i);
4. Kết hợp thuật toán Dijsktra và tìm kiếm theo chiều sâu để giải quyết bài
toán đặt ra
Ý tưởng: Đầu tiên, ta sử dụng tìm kiếm theo chiều sâu để tìm đường đi từ
đỉnh u đến đỉnh v. Tiếp đến, ta đánh dấu các cạnh của đường đi này lại (hoặc coi
như đồ thị không tồn tại các cạnh thuộc đường đi này). Sau đó, ta sử dụng thuật
toán Dijsktra để tìm đường đi ngắn từ đỉnh u đến đỉnh v. Tiếp đến, ta lưu lại kết quả
của hai đường đi này (tổng độ dài của hai đường đi,...) và tiếp tục làm lại từ đầu và
so sánh tổng độ dài của chúng với nhau để ta tìm được hai đường đi thỏa mãn yêu
cầu bài toán là không có cạnh chung và tổng độ dài ngắn nhất.
Để làm rõ ý tưởng trên, chúng tôi sử dụng một ví dụ để mô tả chi tiết ý tưởng
của chúng tôi.
Ví dụ: Cho đồ thị có hình dưới đây
Giả sử đỉnh u = 1 và đỉnh v = 4. Với ý tưởng trên, thực hiện như sau:

12


13

2


3

2

1

1

4

2

3

1
2

1

1

5

6

- Đầu tiên, sử dụng tìm kiếm theo chiều sâu để tìm đường đi từ đỉnh 1 đến
đỉnh 4, ví dụ kết quả tìm kiếm đầu tiên là:
1->2->3->4, có tổng độ dài là: 4
- Tiếp đến, ta đánh dấu các cạnh của đường đi trên trong đồ thị (hoặc tạo ra
đồ thị mới không có các cạnh thuộc đường đi trên). Đồ thị sẽ có dạng như sau:

2

3

2

3

1
2

4
1

1

6

5

- Lúc này ta sử dụng thuật toán Dijsktra để tìm đường đi ngắn nhất từ đỉnh 1
đến đỉnh 4 trong đồ thị trên. Kết quả tìm được sẽ là:
1->6->5->4, có tổng độ dài là: 4
- Như vậy, ta tìm được hai đường đi đầu tiên thỏa mãn điều kiện không có
cạnh chung, đó là:
+ Đường 1: 1->2->3->4, có tổng độ dài là: 4
+ Đường 2: 1->6->5->4, có tổng độ dài là: 4
13



14

Tổng độ dài của hai đường đi là: 8
- Bây giờ ta quay lại bước đầu tiên sử dụng tìm kiếm theo chiêu sâu để tìm
đường đi từ đỉnh 1 đến đỉnh 4 khác và cứ làm như vậy, ta lại được hai đường đi và
so sánh với kết quả của hai đường đi trước nếu kết quả nào có tổng độ dài hai
đường đi nhỏ hơn thì chúng ta lưu lại.
Độ phức tạp của thuật toán
Thuật toán Dijstra có độ phức tạp là O(n^2 + m)
Trong thuật toán DFS, một đường đi từ u đến v được tìm thấy với độ phức
tạp O(n+m) và cần duyệt qua tất cả các đường đi từ u đến v nên độ phức tạp của
hàm DFS là O((n + m)*p) với p là tổng số đường đi từ u đến v.
Thực nghiệm chương trình
Sau khi hoàn thành thuật toán chúng tôi đã thử nghiệm với một số đồ thị và
có kết quả như sau:
Trên máy tính có cấu hình:
- CPU: Core 2 duo, 64bit Intel E6750 2.66GHz
- RAM: 2GB DDRII
Số đỉnh

12

15

20

30

Sổ cạnh


29

41

62

89

Thời gian chạy

1s

3s

250

NA

s

14


15

TÀI LIỆU THAM KHẢO
- Đào Thanh Tĩnh, Các bài giảng môn học Thiết kế và đánh giá thuật toán.
- Một số tài liệu về Lý thuyết đồ thị.
- Một số trang web trên mạng Internet.


15