ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
ĐỒ ÁN MÔN HỌC

GVHD: PGS. TS. Nguyễn Phi Khứ
HVTH: Lê Thành Nguyên
MSHV: CH1301102
Lớp : Cao học Khóa 8
TP HCM, Tháng 06 năm 2014
MÔN: ĐIỆN TOÁN LƯỚI VÀ ĐÁM MÂY
SONG SONG HÓA
THUẬT TOÁN DIJKSTRA
MỤC LỤC
MỤC LỤC i
DANH MỤC HÌNH ii
PHẦN 1: MỞ ĐẦU 1
PHẦN 2: TỔNG QUAN 2
PHẦN 3: SONG SONG HÓA THUẬT TOÁN DIJKSTRA 3
3.1. THUẬT TOÁN DIJKSTRA 3
3.2. VẤN ĐỀ VÀ GIẢI PHÁP 4
3.2.1. Vấn đề 4
3.2.2. Giải pháp 5
PHẦN 4: THỰC NGHIỆM 8
4.1. LÝ THUYẾT 8
4.2. THỰC TẾ 9
PHẦN 5: KẾT LUẬN VÀ KHUYẾN NGHỊ 11
5.1. KẾT LUẬN 11
5.2. KHUYẾN NGHỊ 11
TÀI LIỆU THAM KHẢO 12
i
DANH MỤC HÌNH

Hình 1. Thuật toán Dijkstra 3
Hình 2. Đồ thị thể hiện dung lượng bộ nhớ (MB) tăng theo số đỉnh đồ thị 4
Hình 3. Đồ thị có trọng số G(V, E) 5
Hình 4. Sơ đồ quá trình thực hiện tìm đường đi ngắn nhất 6
Hình 5. Đồ thị G sau khi cắt thành hai đồ thị con 7
Hình 6. Đồ thị tổng hợp tìm đường đi ngắn nhất từ A đến J 7
Hình 7. Biểu đồ so sánh thời gian thực hiện giữa thuật toán Dijkstra tuần tự và song song
9
ii
GVHD: PGS. TS. Nguyễn Phi Khứ HVTH: Lê Thành Nguyên
PHẦN 1: MỞ ĐẦU
Trong thời đại bùng nổ thông tin hiện nay, đồng thời nhằm tăng khả năng đáp ứng
người dùng cũng như tính chính xác của thông tin, dữ liệu thu thập cho một hệ thống
thông tin ngày càng tăng cao. Với sự tăng trưởng không ngừng về quy mô của dữ liệu đã
đặt ra câu hỏi “liệu các hệ thống máy tính mạnh nhất hiện nay có khả năng giải quyết bài
toán này trong thời gian tối ưu hay không?”. Khi điều kiện lý tưởng chỉ có thể xảy ra trên
hệ thống máy tính lượng tử đắt tiền, sứ mệnh đặt ra cho các nhà khoa học máy tính phải
tìm giải pháp thay thế tốt hơn.
Từ đó, các mô hình triển khai mới: điện toán song song, điện toán phân tán, điện
toán lưới, điện toán đám mây,… được khai sinh nhằm đáp ứng nhu cầu xử lý dữ liệu trên
quy mô lớn và làm nền tảng cho lĩnh vực điện toán hiệu năng cao. Từ đây, cách nhìn
nhận về quy mô dữ liệu đã được thay đổi cùng với số lượng lớn bài toán khó được giải
quyết. Tuy nhiên, đa số các thuật toán phải được chuyển đổi từ mô hình triển khai xử lý
tuần tự sang mô hình điện toán mới.
Bài toán tìm đường đi ngắn nhất được ứng dụng trong nhiều lĩnh vực của khoa học
máy tính: xác định đường đi của gói tin trong mạng máy tính, tìm đường đi mạng lưới
giao thông,… và một trong số này được hiện thực bằng thuật toán Dijkstra.
Thuật toán Dijkstra được sử dụng để tìm đường đi ngắn nhất từ đỉnh A đến đỉnh B
trên một đồ thị liên thông G(V, E) có trọng số không âm với độ phức tạp thời gian O(n
2

).
Điều này đồng nghĩa với chi phí của thuật toán sẽ tỉ lệ thuận với số đỉnh trên G. Trong
trường hợp xấu nhất, số đỉnh của đồ thị G quá lớn dẫn đến máy tính không thể thực hiện
được hoặc thời gian chờ kết quả quá lớn làm giảm tính khả thi của thuật toán.
Nhằm cải thiện chi phí trên thuật toán Dijkstra, trong bài viết này sẽ đề xuất hướng
giải quyết dựa trên cách tiếp cận điện toán song song để cải thiện hai vấn đề về không
gian bộ nhớ và thời gian thực thi của thuật toán.
Trang 1
GVHD: PGS. TS. Nguyễn Phi Khứ HVTH: Lê Thành Nguyên
PHẦN 2: TỔNG QUAN
Do được ứng dụng trong nhiều lĩnh vực, bài toán song song hóa thuật toán
Dijkstra đã được nghiên cứu và được công bố trong nhiều công trình của các nhà khoa
học máy tính trên thế giới cũng như tại Việt Nam. Đặc điểm chung của các công trình
này là tìm giải pháp song song hóa các tiến trình tìm đường đi ngắn nhất trên ma trận kề
của đồ thị G(V, E). Bên cạnh đó, sử dụng các thuật toán hỗ trợ trên heap nhằm giảm độ
phức tạp của thuật toán. Chẳng hạn như:
Nghiên cứu “xây dựng thuật toán song song tìm đường đi ngắn nhất với
CUDA”[1] của Nguyễn Việt Đức và Nguyễn Nam Giang trường ĐH Lạc Hồng ứng dụng
kỹ thuật CUDA xây dựng mô hình song song thuật toán Dijkstra, Ford Bellman và Floyd.
Trong nội dung song song hóa thuật toán Dijkstra, tác giả sử dụng bộ vi xử lý đồ họa
GPU dựa trên kỹ thuật CUDA triển khai theo cơ chế SIMD(Single Instruction Mutiple
Data Stream)[4].
Nghiên cứu “A Parallelization of Dijkstra’s Shortest Path Algorithm”[6] của
A.Crauser, K.Mehlhorn, U.Meyer và P. Sanders đã tiến hành song song hóa thuật toán
Dijkstra kết hợp sử dụng thuật toán PRAM xử lý dữ liệu trên heap nhằm giảm độ phức
tạp của thuật toán Dijkstra khi xử lý tuần tự trên từng thread. Từ đó, giảm độ phức tạp
cho thuật toán song song.
Nghiên cứu “Song song hóa thuật toán tìm đường đi ngắn nhất trên nguồn dữ liệu
lớn dùng MPI”[2] của Đặng Như Toàn trường ĐH Lạc Hồng. Tác giả sử dụng mô hình
truyền thông điệp Message Passing Interface – MPI triển khai ứng dụng trên mô hình

MIMD (Multiple Instruction Multiple Data Stream)[4]. Tác giả đã tiến hành chia đồ thị
G thành k thành phần và tiến hành xử lý song song trên k bộ xử lý. Tuy nhiên, tác giả
chưa đưa ra hướng giải quyết những vấn đề phát sinh trong chia cắt đồ thị cũng như quy
trình cụ thể.
Như vậy, đa số nghiên cứu đều tập trung vào vấn đề song song hóa thuật toán
Dijkstra nhưng chưa tập trung vào vấn đề giảm chi phí bộ nhớ máy tính khi tập đỉnh trên
G tăng lên rất lớn. Trong nghiên cứu này sẽ đề xuất phương pháp song song hóa thuật
toán Dijkstra nhằm giảm chi phí thời gian theo hướng tiếp cận chia đồ thị G thành k đồ
thị con G
k
. Đồng thời, giải quyết những vấn đề khi chia tách đồ thị.
Trang 2
GVHD: PGS. TS. Nguyễn Phi Khứ HVTH: Lê Thành Nguyên
PHẦN 3: SONG SONG HÓA THUẬT TOÁN DIJKSTRA
3.1. THUẬT TOÁN DIJKSTRA
Thuật toán Dijkstra do nhà khoa học máy tính người Hà Lan Edsger Dijkstra phát
minh được sử dụng để tìm đường đi ngắn nhất từ một đỉnh v
i
đến v
j
trên một đồ thị
G(V, E) liên thông có trọng số không âm dựa trên ma trận kề của G có độ phức tạp O(n
2
).
DIJKSTRA Algorithm
// Input: v
begin
, v
end
: đỉnh xuất phát, đỉnh kết thúc

// matrix, V: ma trận kề đồ thị G(V, E), tập đỉnh G
// Output: đường đi ngắn nhất từ v
begin
đến v
end
1. d[v
begin
] = 0;
2. for i = 1 to V.length do{
3. Xác định minIndex: d[minIndex] = min(d);
4. check[minIndex] = true;
5. for j = 1 to V.length do{
6. if check[j] == false then
7. d* = d[minIndex] + matrix[minIndex][j]
8. if d* < d[j] then
9. d[j] = d*;
10. pre[j] = v[minIndex];
11. end if;
12. end if;
13. }
14. if check[v
end
] = true then
15. break;
16. end if;
17. }
18. if check[v
end
] = true then
19. result = {v

end
};
20. i = vend;
21. do
22. result[0] = pre[i];
23. i = pre[i];
24. until i = v
begin
;
25. result[0] = v
begin
;
26. return result;
27. else
28. return {};
29. end if;
Hình 1. Thuật toán Dijkstra
Trang 3
GVHD: PGS. TS. Nguyễn Phi Khứ HVTH: Lê Thành Nguyên
3.2. VẤN ĐỀ VÀ GIẢI PHÁP
3.2.1. Vấn đề
Cho đồ thị G(V, E) là đồ thị liên thông có trọng số không âm, bao gồm một tập
đỉnh V được phân bố trong một không gian P, E là tập cạnh liên kết giữa các đỉnh trong
G. Khi đó, độ dài của cạnh v
ij
∈ V là chi phí để di chuyển từ đỉnh i đến đỉnh j, chi phí này
tùy vào từng mục tiêu cụ thể của bài toán có thể là thời gian, khoảng cách, …
Hình 2. Đồ thị thể hiện dung lượng bộ nhớ (MB) tăng theo số đỉnh đồ thị
Như đã đề cập bên trên, thuật toán Dijkstra được sử dụng phổ biến để giải quyết
bài toán tìm đường đi ngắn nhất trên đồ thị G(V, E). Tuy nhiên, với độ phức tạp O(n

2
)
(với n = |V|) khi số đỉnh trên không ngừng tăng lên đã dẫn đến tình trạng sau:
− Thời gian giải quyết vấn đề không thể chấp nhận được.
− Bộ nhớ máy tính không thể đáp ứng được không gian lưu trữ.
Khi đó, thuật toán Dijkstra xem như bất khả thi và cần một phương pháp khác tối
ưu hơn giải quyết vấn đề trên. Ngoài ra, thuật toán Dijkstra triển khai trên máy tính đơn
còn gặp một số nhược điểm sau:
− Trên đồ thị có thể xảy ra biến động, do đó kết quả của lần thực hiện trước
không thể sử dụng ở những lần sau đó.
− Trong trường hợp kết quả tìm đường được lưu trữ, khi xảy ra thay đổi trên đồ
thị phải xóa toàn bộ kết quả và cho hệ thống học lại từ đầu.
Trong nội dung tiếp theo, bài viết sẽ đưa ra giải pháp nhằm tối ưu hóa về thời gian
cũng như không gian lưu trữ trong thời gian thực thi thuật toán Dijkstra.
Trang 4
GVHD: PGS. TS. Nguyễn Phi Khứ HVTH: Lê Thành Nguyên
3.2.2. Giải pháp
Trong thực tế, tập đỉnh V của đồ thị G(V, E) là tập các điểm với tọa độ xác định
phân bố trong một không gian P nhất định. Tuy nhiên, hầu hết các ứng dụng triển khai
thuật toán Dijkstra theo cơ chế song song chưa quan tâm đến vấn đề tọa độ của đỉnh v
i
.
Điều này dẫn đến khó khăn trong phân chia dữ liệu trên ma trận kề.
Với mục tiêu giảm không gian lưu trữ cho thuật toán trên một máy tính trong một
thời điểm, đồ thị G ban đầu sẽ được xem xét nhằm chia nhỏ thành từng bộ phận nhỏ hơn.
Hình 3. Đồ thị có trọng số G(V, E)
Trang 5
6
8
4

10
3
4
5
2
4
2
4
6
14
A
B
C
D
E
F
G
H
I
J
6
7
GVHD: PGS. TS. Nguyễn Phi Khứ HVTH: Lê Thành Nguyên
Do tính xác định của tọa độ trong V, khi hợp tập đỉnh V lớn ta có thể phân chia tập
đỉnh này thành từng cụm có kích thước gần giống nhau. Từ đó, có thể tiến hành xử lý
trên từng cụm đỉnh như một đồ thị và kết quả này được tổng hợp thành kết quả cuối cùng.
Quá trình thực hiện qua các bước sau:
− Bước 1: Chia nhỏ đồ thị G thành k đồ thị con G
k
sao cho kích thước tập đỉnh

trên các đồ thị con G
k
tương đương nhau.
Giả sử tập V chứa các điểm nằm trên cùng một mặt phẳng, do đó G được tiến
hành chia thành m mảnh theo chiều ngang và n mảnh theo chiều dọc (k = m * n). Trong
quá trình này, các điểm tiếp xúc giữa các cạnh của G với đường biên chia tách đồ thị sẽ
được tạo các đỉnh phụ và tiến hành cắt cạnh này thành hai phần từ đỉnh tạm về 2 phía của
biên giới.
− Bước 2: Tiến hành tìm đường đi từ tất cả các đỉnh đến tất cả các đỉnh còn lại
trên các đồ thị con G
i
, các đỉnh tạm tại biên giới của mảnh cắt thuộc cả hai đồ thị con ở
hai phía của biên giới.
Quá trình này được tiến hành song song trên nhiều máy tính, kết quả của quá trình
này được lưu trữ vào cơ sở dữ liệu.
Trang 6
Tìm đường đi ngắn nhất
Tìm đường đi
ngắn nhất trên G
G lớn
Sai Đúng
Tìm đường đi ngắn
nhất trên các đồ thị con
Tìm đường đi ngắn
nhất hoàn chỉnh
Lưu vào CSDL
Thực hiện
lần đầu
Đúng
Cắt G

Sai
Hình 4. Sơ đồ quá trình thực hiện tìm đường đi ngắn nhất
GVHD: PGS. TS. Nguyễn Phi Khứ HVTH: Lê Thành Nguyên
−
− Bước 3: Xây dựng đồ thị chỉ chứa hai đỉnh bắt đầu và đỉnh kết thúc cần tìm
đường đi và tất cả các đỉnh tạm. Độ dài các cạnh trên đồ thị là giá trị đường đi ngắn nhất
tìm được ở bước 2. Sử dụng thuật toán Dijstra tìm đường đi từ đỉnh bắt đầu đến đỉnh kết
thúc.
Thay thế các đoạn đường trong kết quả tìm được có chứa đỉnh tạm bằng đường đi
ngắn nhất giữa hai đỉnh này tìm được trong bước 2.
Trang 7
6
8
4
8
3
4
4
2
4
2
3
6
14
A
B
C
D
E
F

G
H
I
J
2
7
5
1G1
G2
Đỉnh phụ
8
10
15
A
J
12
9
7
10
13
C
E
H
Hình 6. Đồ thị tổng hợp tìm đường đi ngắn nhất từ A đến J
Hình 5. Đồ thị G sau khi cắt thành hai đồ thị con
GVHD: PGS. TS. Nguyễn Phi Khứ HVTH: Lê Thành Nguyên
PHẦN 4: THỰC NGHIỆM
Trong nội dung này, bài viết sẽ đánh giá tốc độ thực thi cũng như không gian bộ
nhớ lý thuyết và thực nghiệm của thuật toán Dijkstra sau khi được triển khai song song
hóa.

4.1. LÝ THUYẾT
− Về thời gian: Như đã đề cập ở phần trên, đồ thị G sẽ được chia thành k đồ thị
con Gk với kích thước tập đỉnh như nhau và được xác định bởi:
Như vậy độ phức tạp về thời gian khi thực hiện trên từng đồ thị con là .
Độ phức tạp về thời gian khi thực hiện quá trình tổng hợp kết quả được xác định
O(|V
P
|
2
) với V
P
là tập đỉnh phụ được tạo ra trong quá trình cắt đồ thị G.
Giả sử có m máy tính mỗi máy tính thực hiện t tiểu trình tìm đường ngắn nhất đồ
thị con trên Gk (m* t ≤ k) ta có độ phức tạp thời gian thuật toán như sau:
T =
Trong điều kiện lý tưởng, nghĩa là từ lần thực hiện thứ hai trở đi độ phức tạp về
thời gian thuật toán được xác định bởi:
− Về không gian: Khi thực thi thuật toán Dijstra trên G bộ nhớ RAM tối thiểu
được xác định như sau:
S = (|V|
2
+ 2.|V|).64 + |V| (bit)
= 64|V|
2
+ 129|V| (bit)
Khi thực hiện trên đồ thị con G
k
, không gian bộ nhớ được xác định bởi:
Trang 8
GVHD: PGS. TS. Nguyễn Phi Khứ HVTH: Lê Thành Nguyên

Trong quá trình tổng hợp đường đi ngắn nhất đầy đủ, không gian bộ nhớ được xác
định theo công thức:
Như vậy, đồ thị G sau khi chia nhỏ có càng ít điểm trung gian khi đó sẽ giảm đáng
kể chi phí cả về không gian lưu trữ lẫn thời gian thực hiện.
4.2. THỰC TẾ
Để kiểm nghiệm tính khả thi của thuật toán Dijkstra sau khi được song song hóa,
tác giả đã triển khai thử nghiệm với hệ thống máy tính trong mạng LAN gồm 20 máy với
các thông số sau:
− Hệ điều hành Windows XP, RAM 512MB, CPU Intel Pentium 3.2 GHz.
− Java Runtime Environment 1.6
− Hệ quản trị Cơ sở dữ liệu: PostgreSQL 8.2 + PostGIS 1.8.4
− Đồ thị G được phát sinh ngẫu nhiên n đỉnh và chia thành k đồ thị con có kích
thước tập đỉnh |V
k
| ∈ (100, 120).
− Tốc độ mạng LAN tối đa 100Mbs.
Trong quá trình thử nghiệm, với mỗi đồ thị được phát sinh thực hiện mỗi thuật
toán 10 lần ta có đồ thị như Hình 7.
Hình 7. Biểu đồ so sánh thời gian thực hiện giữa thuật toán Dijkstra tuần tự và song song
Từ biểu đồ ở Hình 7. cho thấy:
Trang 9
GVHD: PGS. TS. Nguyễn Phi Khứ HVTH: Lê Thành Nguyên
− Khi kích thước tập đỉnh V của đồ thị nhỏ, thời gian thực thị yêu cầu theo mô
hình tuần tự nhanh hơn mô hình song song.
− Khi kích thước tập V tăng cao, thuật toán Dijkstra song song hiệu quả hơn và
có độ tăng thời gian chậm hơn thuật toán Dijkstra tuần tự.
Trang 10
GVHD: PGS. TS. Nguyễn Phi Khứ HVTH: Lê Thành Nguyên
PHẦN 5: KẾT LUẬN VÀ KHUYẾN NGHỊ
5.1. KẾT LUẬN

Đề tài đã cài đặt và thử nghiệm thành công thuật Dijkstra giải bài toán tìm đường
đi ngắn nhất trên môi trường điện toán song song và đạt được một số kết quả sau:
− Phân chia đồ thị G thành k đồ thị con G
k
độc lập.
− Thuật toán áp dụng cho toàn hệ thống là thuật toán Dijkstra triển khai trên máy
tính đơn.
− Kết quả tìm đường được lưu trữ và sử dụng cho những lần sau.
− Trong trường hợp đồ thị G có biến động, chỉ phải xóa phần đường đi nằm trên
mảnh G
k
có thay đổi.
Ý tưởng phân chia đồ thị thành các đồ thị con dựa vào tọa độ của tập đỉnh đã
mang lại hiệu quả trong tối ưu thuật toán Dijkstra dựa trên mô hình triển khai MIMD[4].
5.2. KHUYẾN NGHỊ
Nhằm thừa hưởng thành quả nghiên cứu trong khoa học máy tính với sự ra đời của
của điện toán song song, điện toán phân tán, điện toán lưới và đám mây. Đồng thời, để
đánh giá và hoàn thiện nghiên cứu này đề nghị được triển khai trong một nghiên cứu cao
hơn.
Bên cạnh đó, hầu hết các lĩnh vực áp dụng thuật toán Dijkstra trong tìm đường đi
ngắn nhất trên đồ thị G có tập đỉnh V chứa các điểm có tọa độ xác định trong không gian
P, nhằm kiểm nghiệm tính đúng đắn của nghiên cứu này cần phải phát triển trên một đồ
thị G có thật, chẳng hạn như tìm đường đi trên mạng lưới giao thông ở TP.Hồ Chí Minh.
Trang 11
GVHD: PGS. TS. Nguyễn Phi Khứ HVTH: Lê Thành Nguyên
TÀI LIỆU THAM KHẢO
1. Nguyễn Việt Đức, Nguyễn Nam Giang, “Xây dựng thuật toán song song tìm
đường đi ngắn nhất với CUDA”.
2. Đặng Như Toàn (2011), Song song hóa thuật toán tìm đường đi ngắn nhất trên
nguồn dữ liệu lớn dùng MPI, Luận văn Thạc sỹ Công nghệ thông tin, Trường Đại

học Lạc Hồng, Đồng Nai.
3. S. Justin Samuel, M. Gnana Sagaya Sharmila(2014), “Improved Shortest Path
Method to Select the Best Path from Multi-Path Web Services Composition
Graph”, IJCSIT, Vol5(2), pg. 1227 – 1231.
4. Fayez Gebali (2011), Algoriths and Parallel Computing, Jonh Wiley & Sons, Inc.
5. R. Kalpana and P. Thambidurai (2011), “Combining speedup Techniques based on
Landmarks and Containers with parallelised preprocessing in Random and Planar
Graphs”, IJCSIT, Vol.3(1), pg. 152 – 171.
6. A.Crauser, K.Mehlhorn, U.Meyer, P. Sanders, “A Parallelization of Dijkstra’s
Shortest Path Algorithm”, Max-Plack-Institut fur Informatik, Gemany.
Trang 12