BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC NÔNG LÂM THÀNH PHỐ HỒ CHÍ MINH
KHÓA LUẬN TỐT NGHIỆP
CẢI TIẾN THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
TRÊN ĐỒ THỊ PHẲNG ÁP DỤNG THÍ ĐIỂM TẠI
THÀNH PHỐ HỒ CHÍ MINH
Họ và tên sinh viên: NGUYỄN QUỐC HOÀNG
Ngành: Hệ thống Thông tin Địa lý
Niên khóa: 2013 – 2017
Tháng 6/2017
CẢI TIẾN THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
TRÊN ĐỒ THỊ PHẲNG ÁP DỤNG THÍ ĐIỂM TẠI
THÀNH PHỐ HỒ CHÍ MINH
Tác giả
NGUYỄN QUỐC HOÀNG
Khóa luận được đệ trình để đáp ứng yêu cầu
cấp bằng Kĩ sư ngành Hệ thống Thông tin Địa lý
Giáo viên hướng dẫn:
Th.S Khưu Minh Cảnh
Tháng 6 năm 2017
LỜI CẢM ƠN
Trước hết, tôi xin chân thành cảm ơn thầy Th.S Khưu Minh Cảnh, cán bộ công tác
tại Sở Khoa học và Công nghệ thành phố Hồ Chí Minh, người đã trực tiếp hướng dẫn tôi
hoàn thành đề tài tốt nghiệp này. Cảm ơn thầy đã tận tình chỉ bảo, hỗ trợ, chia sẻ kinh
nghiệm và động viên tôi trong suốt thời gian qua về bài luận.
Tôi cũng xin chân trọng cảm ơn Ban lãnh đạo Sở Khoa học và Công nghệ thành phố
Hồ Chí Minh đã tạo điều kiện cho tôi được thực tập, làm việc tại quý cơ quan. Đặc biệt,
tôi xin gửi lời cảm ơn đến phòng Trung tâm Ứng dụng Hệ thống Thông tin Địa lý
TP.HCM (HCMGIS) nói chung, anh Lê Võ Hữu Trí nói riêng, đã tận tình trao đổi các
kiến thức, kinh nghiệm quý báu cũng như chia sẻ tài liệu, dữ liệu trong quá trình thực hiện
bài luận.
Tôi xin gửi lời tri ân sâu sắc đến thầy PGS.TS Nguyễn Kim Lợi, thầy Th.S Lê Văn
Phận, cô Th.S Nguyễn Thị Huyền, thầy KS. Nguyễn Duy Liêm, quý thầy cô trường đại
học Nông Lâm thành phố Hồ Chí Minh cùng với tập thể lớp DH13GI. Cảm ơn quý thầy
cô, quý anh chị và các bạn về những kiến thức, kinh nghiệm và sự giúp đỡ chân tình đã
dành cho tôi trong suốt bốn năm học tập tại trường.
Nguyễn Quốc Hoàng – DH13GI
Khoa Môi trường và Tài nguyên
Trường Đại học Nông Lâm TP. Hồ Chí Minh
Số điện thoại: 0983282294
Email:
[email protected]
i
TÓM TẮT
Đề tài nghiên cứu "Khai thác các tính chất cho bài toán tìm đường đi trên mặt
phẳng" đã được thực hiện trong thời gian từ tháng 03/2017 đến tháng 06/2017. Mục tiêu
đề tài là có thể ứng dụng được các thuật toán tìm đường đi ngắn nhất trên đồ thị phẳng,
xây dựng công cụ tìm đường đi kết hợp ứng dụng WEBGIS liên kết với các thuật toán đã
nghiên cứu.
Phương pháp tiếp cận của đề tài là sử dụng công nghệ GIS, sử dụng phần mềm
ArcGIS xây dựng biên tập dữ liệu về mạng lưới đường giao thông tại Thành phố Hồ Chí
Minh, tiến hành phân loại và thống kê, phân tích chia nhỏ các đoạn đường dùng đó làm cơ
sở để phục vụ nghiên cứu. Bên cạnh đó, tìm hiểu về các thuật toán tìm đường đi, dựa vào
các dữ liệu đã biên tập xây dựng ma trận kề, từ đó tiến hành mô phỏng đồ thị. Kết hợp
ngôn ngữ lập trình Python, Visual Studio Code xây dựng web trên Geoserver tích hợp
được bản đồ và các thuật toán xây dựng công cụ tìm kiếm đường đi ngắn nhất.
Đề tài nghiên cứu đã đạt được các kết quả sau:
- Nghiên cứu lý thuyết đồ thị và các thuật toán tìm đường đi trên đồ thị phẳng.
- Xây dựng được cơ sở dữ liệu GIS về mạng lưới giao thông, phân loại và thống kê
hệ thống đường giao thông tại Thành phố Hồ Chí Minh. Chia cắt đường thành các phân
đoạn, tính toán được độ dài các đoạn đường phục vụ cho việc tính toán thuật toán.
- Ứng dụng thành công thuật toán xây dựng công cụ tìm kiếm đường đi ngắn nhất.
- Xây dựng thiết kế giao diện web có công cụ tìm kiếm với các thuật toán đã cài đặt.
ii
MỤC LỤC
LỜI CẢM ƠN ........................................................................................................................ i
TÓM TẮT.............................................................................................................................ii
MỤC LỤC .......................................................................................................................... iii
DANH MỤC BẢNG BIỂU .................................................................................................. v
DANH MỤC HÌNH ẢNH ................................................................................................... vi
CHƯƠNG 1. MỞ ĐẦU ........................................................................................................ 1
1.1. Tính cấp thiết của đề tài................................................................................................. 1
1.2. Mục tiêu nghiên cứu ...................................................................................................... 1
1.3. Đối tượng và phạm vi nghiên cứu ................................................................................. 1
CHƯƠNG 2. TỔNG QUAN TÀI LIỆU .............................................................................. 2
2.1. Khu vực nghiên cứu ...................................................................................................... 2
2.1.1. Vị trí địa lý ............................................................................................................. 2
2.1.2. Hạ tầng giao thông ................................................................................................. 3
2.2. Bài toán tìm đường đi ngắn nhất ................................................................................... 3
2.2.1. Lý thuyết đồ thị ...................................................................................................... 3
2.2.2. Bài toán tìm đường đi ngắn nhất ............................................................................ 7
2.3. Các thuật toán tìm đường đi ngắn nhất.......................................................................... 7
2.3.1. Thuật toán Dijkstra ................................................................................................. 7
2.3.2. Thuật toán Bellman .............................................................................................. 11
2.3.3. Thuật toán Floyd – Warshall ................................................................................ 13
2.3.4. Thuật toán Fox nhân ma trận ............................................................................... 16
2.4. Các công nghệ nền tảng ............................................................................................... 21
2.4.1. Python .................................................................................................................. 21
2.4.2. Hệ quản trị cơ sở dữ liệu PostgreSQL/PostGIS ................................................... 22
2.4.3. Phần mềm Visual Studio Code ............................................................................ 22
2.5. Tình hình nghiên cứu có liên quan .............................................................................. 23
iii
CHƯƠNG 3. DỮ LIỆU VÀ PHƯƠNG PHÁP NGHIÊN CỨU ........................................ 24
3.1. Dữ liệu ......................................................................................................................... 24
3.2. Phương pháp ................................................................................................................ 27
3.2.1. Phân loại và thống kê các loại đường .................................................................. 28
3.2.2. Cắt đường và tính độ dài các phân đoạn .............................................................. 29
3.2.3. Xây dựng đồ thị .................................................................................................... 31
3.2.4. Xây dựng ma trận kề của các đỉnh ....................................................................... 32
3.2.5. Thuật toán tìm đường đi Dijkstra sửa đổi ............................................................ 33
3.2.6. Thuật toán tìm đường đi Floyd sửa đổi ................................................................ 36
3.2.7. Xây dựng trang web ............................................................................................. 37
3.2.7.1. Xây dựng cơ sở dữ liệu ..................................................................................... 37
3.2.7.2. Xây dựng thiết kế web ...................................................................................... 40
CHƯƠNG 4. KẾT QUẢ NGHIÊN CỨU .......................................................................... 41
4.1. Phân loại và thống kê các loại đường .......................................................................... 41
4.2. Độ dài các phân đoạn đường ....................................................................................... 43
4.3. Đồ thị về không gian nghiên cứu ................................................................................ 48
4.4. Ma trận kề của các đỉnh thuộc khu vực nghiên cứu .................................................... 48
4.5. Kết quả cải tiến thuật toán ........................................................................................... 49
4.6. Kết quả xây dựng trang web ........................................................................................ 49
CHƯƠNG 5. KẾT LUẬN, KIẾN NGHỊ ........................................................................... 58
5.1. Kết luận........................................................................................................................ 58
5.2. Kiến nghị ..................................................................................................................... 58
TÀI LIỆU THAM KHẢO .................................................................................................. 59
PHỤ LỤC ........................................................................................................................... 61
iv
DANH MỤC BẢNG BIỂU
Bảng 2.1. Các chức năng Visual Studio Code phụ thuộc vào ngôn ngữ……..………22
Bảng 3.1. Mô tả dữ liệu thu thập……………………………………………….………24
Bảng 4.1. Các loại đường chính nằm trong hệ thống phân loại đường lộ ................... 41
Bảng 4.2. Số lượng các loại đường trong TP.HCM ....................................................... 42
Bảng 4.3. Mô tả độ dài của các phân đoạn đường ......................................................... 47
v
DANH MỤC HÌNH ẢNH
H nh 2.1. Bản đồ ranh giới hành chính TP.HCM ........................................................... 2
H nh 2.2. Mô tả các loại đồ thị ........................................................................................... 5
H nh 2.3. Mô tả đồ thị liên thông ...................................................................................... 6
H nh 2. . Mô tả đồ thị song liên thông, cạnh cầu, đỉnh khớp ......................................... 6
H nh 2.5. Python trong ArcGis 10.3 ................................................................................ 21
H nh 3.1.Bản đồ ranh giới quận huyện của TP.HCM................................................... 25
H nh 3.2.Bản đồ đường giao thông TP.HCM ................................................................ 26
H nh 3.3. Sơ đồ phương pháp nghiên cứu ...................................................................... 27
H nh 3. .Dữ liệu đường OSM .......................................................................................... 28
H nh 3. .Bảng thuộc tính dữ liệu OSM .......................................................................... 28
H nh 3.6.Dữ liệu phân loại đường ................................................................................... 29
H nh 3.7.Công cụ Clip ...................................................................................................... 30
H nh 3. .Cắt đường tại các giao điểm............................................................................. 30
H nh 3. .Đo chiều dài các phân đoạn sau khi cắt đường .............................................. 31
H nh 3.10.Đánh dấu đỉnh lên bản đồ .............................................................................. 32
H nh 3.11.Các t ọng số ..................................................................................................... 32
H nh 3.12.Mô tả đỉnh nguồn, đích và các điểm lân cận ................................................ 35
H nh 3.13. Sơ đồ xây dựng cơ sở dữ liệu ........................................................................ 37
H nh 3.1 . Kết nối dữ liệu lên GeoSe ve ....................................................................... 37
H nh 3.1 . Chồng lớp dữ liệu ........................................................................................... 38
H nh 3.16. Chỉnh sửa hiển thị cho các laye ................................................................... 38
H nh 3.17. Dữ liệu được kết nối lên Postg eSQL........................................................... 39
H nh 3.1 . T uy vấn dữ liệu để hiển thị lên web............................................................ 39
H nh 3.1 . Xây dựng web t ên Visual Studio Code ....................................................... 40
H nh .1. Dữ liệu OSM sau khi phân loại...................................................................... 43
H nh .2. Bản đồ giao thông Quận 3 ............................................................................... 44
vi
H nh .3. Bản đồ giao thông Quận Thủ Đức .................................................................. 45
H nh . . Đường giao thông được cắt tại các điểm giao nhau t ên địa bàn Quận 3 .. 46
H nh . . Đường giao thông được cắt tại các điểm giao trên địa bàn Quận Thủ Đức
............................................................................................................................................ 46
H nh .6. Bảng thuộc tính đo độ dài đoạn đường sau khi cắt ...................................... 47
H nh .7. Đồ thị được xây dựng trong ArcGis ............................................................... 48
H nh . . Ma trận kề của các đỉnh ................................................................................. 48
H nh . . So sánh kết quả thuật toán nguyên bản và cải tiến ...................................... 49
H nh .10. Layer nền t ên GeoSe ve ............................................................................. 50
H nh .11. Laye đường giao thông ................................................................................ 51
H nh .12. Laye các điểm ............................................................................................... 52
H nh .13. Laye đồ thị kết nối ........................................................................................ 52
H nh .1 . Các laye sau khi được chồng lớp ................................................................ 53
H nh .1 . Dữ liệu được đưa vào Postg eSQL ............................................................. 54
H nh .16. Giao diện của trang web.............................................................................. 55
H nh .17. Công cụ phóng to, thu nhỏ bản đồ ............................................................... 55
H nh .1 . Giao diện nơi nhập vị t í và chọn thuật toán .............................................. 56
H nh .1 . Giao diện nơi xuất kết quả tính toán ........................................................... 56
H nh .20. Giao diện nút hiển thị kết quả lên bản đồ ................................................... 56
H nh .21. Giao diện khung hiển thị các thông số về giao thông ................................. 57
vii
CHƯƠNG 1. MỞ ĐẦU
1.1. Tính cấp thiết của đề tài
Sự phát triển của mạng lưới giao thông đường bộ là một tín hiệu đáng mừng, phần
nào cho thấy hình ảnh của nền kinh tế thành phố đang ngày càng tăng trưởng. "Trong giao
thông, lưu thông qua những đoạn đường nào để rút ngắn thời gian tối đa, tiết kiệm được
nhiên liệu là việc hết sức quan trọng và cần thiết". Cũng chính vì thế mà tìm đường đi
ngắn nhất là vấn đề ngày càng được nhiều người quan tâm và sử dụng.
Các thuật toán tìm đường đi hiện nay rất phong phú, mỗi thuật toán có một ưu,
nhược điểm khác nhau. Tuy nhiên, khi cài đặt các thuật toán thường sử dụng hết toàn bộ
bộ nhớ khi tiến hành việc tìm kiếm đường đi.
Trong bối cảnh công nghệ GIS ngày càng được áp dụng rộng rãi trong nhiều lĩnh
vực như: Tài nguyên thiên nhiên, quy hoạch sử dụng đất, thiết kế các mô hình tối ưu trong
việc quy hoạch cơ sở hạ tầng… Cùng với sự phổ biến của ngôn ngữ lập trình Python thì
việc kết hợp GIS và Python nhằm giải quyết vấn đề giảm thiểu bộ nhớ khi cài đặt các
thuật toán tìm đường đi hoàn toàn có khả năng thu được những kết quả như mong đợi.
Đường giao thông tại Thành phố Hồ Chí Minh tương đối bằng phẳng, nên có thể
xem như tương đồng với một đồ thị phẳng. Vì vậy, có thể chọn Thành phố Hồ Chí Minh
là khu vực để áp dụng thí điểm các kết quả nghiên cứu vào thực tế.
Xuất phát từ những lý do trên, đề tài “Cải tiến thuật toán tìm đường đi ngắn nhất
trên đồ thị phẳng áp dụng thí điểm tại Thành phố Hồ Chí Minh” đã được thực hiện.
1.2. Mục tiêu nghiên cứu
Ứng dụng các thuật toán tìm đường đi ngắn nhất (Floyd – Bellman – Dijkstra) trên
đồ thị phẳng.
Xây dựng lớp dữ liệu tìm đường đi.
Cải tiến và cài đặt thuật toán tìm đường đi.
Xây dựng công cụ “Tìm đường đi” trên web với thuật toán cài đặt.
1.3. Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu: Đường giao thông
Phạm vi nghiên cứu: Thành phố Hồ Chí Minh
1
CHƯƠNG 2. TỔNG QUAN TÀI LIỆU
2.1. Khu vực nghiên cứu
2.1.1. Vị t í địa lý
H nh 2.1. Bản đồ ranh giới hành chính TP.HCM
2
Thành phố Hồ Chí Minh nằm trong toạ độ địa lý khoảng 100 10’ – 100 38’ vĩ độ
bắc và 1060 22’ – 1060 54’ kinh độ đông. Thành phố Hồ Chí Minh giáp 6 tỉnh gồm:
Phía Bắc giáp tỉnh Bình Dương.
Tây Bắc giáp tỉnh Tây Ninh.
Đông và Đông Bắc giáp tỉnh Đồng Nai.
Đông Nam giáp tỉnh Bà Rịa -Vũng Tàu.
Tây và Tây Nam giáp tỉnh Long An và Tiền Giang.
Thành phố cách thủ đô Hà Nội gần 1.730km đường bộ, nằm ở ngã tư quốc tế giữa
các con đường hàng hải từ Bắc xuống Nam, từ Ðông sang Tây, là tâm điểm của khu vực
Đông Nam Á. Tính theo đường chim bay thì trung tâm thành phố cách bờ biển Đông 50
km, sân bay quốc tế Tân Sơn Nhất cách trung tâm thành phố 7km, chiều dài của thành
phố theo hướng Tây Bắc – Đông Nam khoảng 100 km và chiều ngang nơi rộng nhất là
hơn 40 km. Thành phố Hồ Chí Minh gồm có bốn điểm cực:
Cực Bắc là xã Phú Mỹ Hưng, huyện Củ Chi.
Cực Tây là xã Thái Mỹ, huyện Củ Chi.
Cực Nam là xã Long Hòa, huyện Cần Giờ.
Cực Đông là xã Thạnh An, huyện Cần Giờ.
2.1.2. Hạ tầng giao thông
Theo thống kê của Sở Giao thông Vận tải: "Tổng chiều dài đường bộ trong Thành
phố là 3.670 km với 3.800 tuyến đường (không kể các tuyến đường khu vực nông thôn),
phần lớn các tuyến đường đều hẹp, chỉ có khoảng 14% số đường có mặt đường rộng trên
12m để có thể vận chuyển hành khách bằng xe buýt thuận lợi, 51% số đường có lòng
đường rộng từ 7-12m, 35% so đường còn lại có lòng đường rộng dưới 7m".
2.2. Bài toán t m đường đi ngắn nhất
2.2.1. Lý thuyết đồ thị
Lịch sử h nh thành:
Lý thuyết đồ thị là 1 lĩnh vực đã có từ lâu và có nhiều ứng dụng hiện đại. Những tư
tưởng cơ bản của lý thuyết đồ thị được đề xuất vào những năm đầu thế kỷ 18 bởi nhà toán
học người Thuỵ Sỹ Lenhard Eurler. Chính ông là người sử dụng đồ thị để giải bài toán
nổi tiếng về các cây cầu ở thành phố Konigberg.
Năm 1845, Gustav Kirchhoff đưa ra Định luật Kirchhoff cho mạch điện để tính điện
thế và cường độ dòng điện trong mạch điện.
3
Năm 1852, Francis Guthrie đưa ra bài toán về vấn đề liệu chỉ với bốn màu có thể tô
màu một bản đồ bất kì sao cho không có hai nước nào cùng biên giới được tô cùng màu
và chỉ được giải vào năm 1976 bởi Kenneth Appel và Wolfgang Haken.
Ứng dụng của lý thuyết đồ thị:
Xác định tính liên thông trong một mạng máy tính: hai máy tính nào đó có thể
truyền dữ liệu cho nhau được không.
Tìm đường đi ngắn nhất trên mạng giao thông
Giải các bài toán tối ưu: lập lịch, phân bố tần số cho các trạm phát thanh, truyền
hình.
Giải bài toán tô màu trên bản đồ: tìm số màu ít nhất để tô các quốc gia sao cho hai
quốc gia kề nhau phải được tô khác màu.
Lý thuyết đồ thị được ứng dụng nhiều trong phân tích lưới. Có hai kiểu phân tích
lưới. Kiểu thứ nhất là phân tích để tìm các tính chất về cấu trúc của một lưới. Kiểu thứ
hai, phân tích để đo đạc, chẳng hạn mức độ lưu thông xe cộ trong một phần của mạng
lưới giao thông
Định nghĩa đồ thị:
Đồ thị là 1 cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này. Chúng ta
phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối 2 đỉnh nào đó của đồ
thị.
Phân loại đồ thị:
Cho đồ thị G = (V, E):
- 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.
- 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.
- G 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 v, u. 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).
- G 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).
4
H nh 2.2. Mô tả các loại đồ thị
Đồ thị phẳng:
Đồ thị được gọi là đồ thị phẳng nếu ta có thể vẽ nó trên mặt phẳng sao cho các
cạnh của nó không cắt nhau ở ngoài đỉnh và chỉ cắt nhau tại đỉnh.
Ứng dụng đồ thị phẳng:
-
-
-
Một trong những bài toán dựa trên đồ thị phẳng là tô màu bản đồ. Bản đồ được mô
tả dưới dạng đồ thị phẳng, mỗi vùng miền trong bản đồ biểu diễn bằng 1 đỉnh, 2
vùng miền kề nhau có màu tô khác nhau. Đồ thị được tô màu sao cho cặp đỉnh kề
nhau có màu tô khác nhau, tìm số màu ít nhất để tô đồ thị.
Đồ thị liên thông:
Đồ thị liên thông: Một đồ thị được gọi là liên thông (connected) nếu có đường đi
giữa mọi cặp đỉnh phân biệt của đồ thị. Ngược lại, đồ thị này được gọi là không
liên thông (disconnected).
Một đồ thị liên thông là 1 đồ thị chỉ có 1 thành phần liên thông.
Một đồ thị không liên thông sẽ bao gồm nhiều đồ thị con liên thông, các đồ thị con
này được gọi là các thành phần liên thông (connected component). Đồ thị liên
thông khi và chỉ khi có một thành phần liên thông.
Tính chất của đồ thị liên thông:
Đồ thị liên thông có hướng:
-
Liên thông mạnh (strongly connected): Đồ thị có hướng gọi là liên thông mạnh
nếu có đường đi từ a tới b và từ b tới a với mọi cặp đỉnh a và b của đồ thị.
-
Liên thông yếu (weakly connected): Đồ thị có hướng gọi là liên thông yếu nếu có
đường đi giữa 2 đỉnh bất kỳ của đồ thị vô hướng nền. Vô hướng nền là bỏ các
hướng của đồ thị có hướng đi.
5
-
Liên thông một phần (unilaterally connected): Đồ thị có hướng gọi là liên thông
một phần nếu với mọi cặp đỉnh a, b bất kỳ, có ít nhất một đỉnh đến được đỉnh còn
lại
H nh 2.3. Mô tả đồ thị liên thông
-
-
Đỉnh khớp (cut vertex/ articulation point): của một đồ thị vô hướng là đỉnh mà nếu
xóa đỉnh này khỏi đồ thị và các cạnh nối đến nó thì số thành phần liên thông của
đồ thị sẽ tăng thêm.
Cạnh cầu (bridge): của một đồ thị vô hướng là cạnh mà nếu xóa đi khỏi đồ thị thì
số thành phần liên thông của đồ thị sẽ tăng thêm.
Đồ thị song liên thông (biconnectivity): là đồ thị không chứa đỉnh khớp.
H nh 2.4. Mô tả đồ thị song liên thông, cạnh cầu, đỉnh khớp
6
2.2.2. Bài toán t m đường đi ngắn nhất
Trong lý thuyết đồ thị, bài toán đường đi ngắn nhất nguồn đơn là bài toán tìm
một đường đi giữa hai đỉnh sao cho tổng các trọng số của các cạnh tạo nên đường đi đó là
nhỏ nhất.
Ví dụ: Cho trước một đồ thị có trọng số là một tập đỉnh V, một tập cạnh E, và một
hàm trong số có giá trị thực f : E → R), cho trước một đỉnh v thuộc V, tìm một đường
đi P từ v tới mỗi đỉnh v' thuộc V sao cho
là nhỏ nhất trong tất cả các đường nối từ v tới v'
Bài toán đường đi ngắn nhất giữa mọi cặp đỉnh là một bài toán tương tự, trong đó ta
phải tìm các đường đi ngắn nhất cho mọi cặp đỉnh.
Trong các ứng dụng thực tế, bài toán tìm đường đi ngắn nhất giữa hai đỉnh của một
đồ thị có một ý nghĩa to lớn. Ví dụ, bài toán chọ một hành trình tiết kiệm nhất ( theo tiêu
chuẩn hoặc khoảng cách, thời gian hoặc chi phí ) trên một mạng giao thông đường bộ,
đường thuỷ hoặc đường không, bài toán chọn một phương pháp tiết kiệm nhất để đưa ra
một hệ thống động lực từ trạng thái xuất phát đến trạng thái đích, bài toán lập lịch thi
công các công đoạn trong một công trình thi công lớn, bài toán lựa chọn đường truyền tin
với chi phí nhỏ nhất trong mạng thông tin, v.v… Hiện nay có rất nhiều các phương pháp
để giải các bài toán như vậy. Thông thường, các thuật toán được xây dựng dựa trên cơ sở
lý thuyết đồ thị là các thuật toán có hiệu quả lớn nhất.
2.3. Các thuật toán t m đường đi ngắn nhất
2.3.1. Thuật toán Dijkst a
Lịch sử:
Thuật toán Dijkstra mang tên của nhà khoa học máy tính người Hà Lan Edsger
Dijkstra vào năm 1956 và ấn bản năm 1959.
Mô tả thuật toán:
Là một thuật toán giải quyết bài toán đường đi ngắn nhất nguồn đơn trong một đồ
thị có hướng không có cạnh mang trọng số âm.
Thuật toán:
Cho đồ thị G (X, E) với các cạnh có trọng số không âm:
X là tập các đỉnh
E là tập các cạnh
Lij là đường đi từ i đến j, với i, j X
: là đường đi ngắn nhất từ đỉnh 1 đến đỉnh i
7
: là giá trị tạm thời của
Tìm đường đi ngắn nhất từ đỉnh 1 tới các đỉnh còn lại ?
Bước 1:
S=X
Bước 2: Chọn
,
S \{j} S
Nếu S =
Nếu S
Bước 3: Cho i = Pj
Đặt P =
Nếu
Trở lại bước 2
Ví dụ: T m đường đi ngắn nhất từ 1 tới các đỉnh còn lại ?
4
2
4
7
2
4
1
5
2
2
6
2
3
1
3
6
5
8
Bước 1:
S=X= { 1,2,3,4,5,6}
1
2
3
4
5
6
0
Bước 2: j = 1,
S
S \ {1} = { 2,3,4,5,6 }
Bước 3:
Gán lại :
Min {
,
= Min { , 7 } = 7
Min {
,
+
+
}
}
= Min { , 1 } = 1
Bước 2: j = 3 ,
S
S \ {3} = { 2,4,5,6 }
Bước 3:
Gán lại :
Min {
,
+
= Min { 7, 1+4 } = 5
Min {
,
+
}
}
= Min { , 1+6 } = 7
Min {
,
+
= Min { , 1+2 } = 3
Đánh dấu đỉnh : 2(5,3)
5(7,3) 6(3,3)
9
}
1
2
3
0
(7,1)
(1,1)
0
(5,3)
(1,1)
4
5
6
(7,3)
(3,3)
0
Bước 2: j = 6,
S
S \ {6} = {2,4,5}
Bước 3:
Gán lại :
Min {
,
+
= Min {5, 3+2} = 5
Min {
,
+
}
}
= Min { , 3+5} = 8
Đánh dấu đỉnh : 2(5,6)
4(8,6)
Bước 2: j = 2,
S
S \ {6} = {4,5}
Bước 3:
Gán lại :
Min {
,
+
= Min {8, 5+4} = 8
Min {
,
+
}
}
= Min {7, 5+2} = 7
Bước 2: j = 5,
S
S \ {5} = {4}
Bước 3:
Gán lại :
Min {
,
+
10
}=7
Kết quả:
1
2
3
0
(7,1)
(1,1)
0
(5,3)
(1,1)
0
(5,3)
(1,1)
4
5
6
(7,3)
(3,3)
(7,3)
(3,3)
0
(8,6)
2
4
1
1
2
5
4
6
3
6
5
2.3.2. Thuật toán Bellman
Lịch sử:
Thuật toán Bellman hay còn gọi là thuật toán Bellman-Ford do hai tác giả là
Bellman và Ford đưa ra
Mô tả thuật toán:
Là một thuật toán giải quyết bài toán đường đi ngắn nhất nguồn đơn trong một đồ
thị có hướng có cạnh mang trọng số âm.
Thuật toán:
Tìm đường đi ngắn nhất từ đỉnh 1 tới các đỉnh còn lại, chứng tỏ đồ thị có mạch âm?
Bước 1:
Bước 2:
{
Bước 3: Nếu
=
nhất từ 1 đến i qua tối đa k đỉnh
},j
, thì
Pi
chính là độ dài đường đi ngắn
Nếu k < n thì tăng k = k + 1 và trở lại bước 2
Nếu k = n thì dừng lại vì đồ thị có mạch âm
11
.PDF 
79 
185 
104 
