Đối tượng bài viết
Dành cho những bạn mới bắt đầu tìm hiểu về những giải thuật
tìm đường, những thắc mắc xoay quanh vấn đề tìm đường đi ngắn nhất.
Loạt bài viết sẽ bao gồm 4 phần:
Phần 1: Giải thuật Dijkstra.
Phần 2: Giải thuật Dijkstra với Fibonacci Heap.
Phần 3: Giải thuật Dijkstra với giải pháp Contraction
hierarchies.
Phần 4: Hướng dẫn hiện thực bài toán tìm đường
đi với bản đồ địa lý.
Phạm vi bài viết
Bài viết được tham khảo từ nguồn http://en.wikipedia.org/wiki/Dijkstra's_algorithm,
qua đó tôi đã bỏ đi một số nội dung vì xét thấy chưa phù hợp với người vừa bắt
đầu tìm hiểu các vấn đề trong bài toán tìm đường đi ngắn nhất.
Bài viết sẽ hướng dẫn demo với C++ tuy nhiên có thể cài đặt
tương tự với những ngôn ngữ khác.
Giới thiệu tổng quan
Thuật toán Dijkstra được phát minh bởi nhà khoa học Edsger
Dijkstra vào năm 1956 và chính thức công bố vào năm 1959, giúp giải quyết bài
toán tìm kiếm đường đi nhắn nhất trên đồ thị không có trọng số âm.
Mục tiêu của thuật
toán:
Từ một đỉnh xuất phát của đồ thị, thuật toán sẽ giúp tìm được
đường đi ngắn nhất với các đỉnh còn lại, hoặc với 1 đỉnh đích duy nhất. Ví dụ:
nếu xem những thành phố là một đỉnh của đồ thị, đường đi lại giữa 2 thành phố
là cạnh của đồ thị, Dijkstra sẽ giúp tìm đường đi ngắn nhất từ thành phố A đến
thành phố B.
Đánh giá hiệu năng của
thuật toán:
STT
|
Thuật toán
|
Độ phức tạp
|
1
|
Dijkstra với lưu trữ hàng đợi không ưu tiên
|
 |
2
|
Dijkstra với Fibonacci heap (sẽ được đề cập ở bài viết sau)
|
 |
Tư tưởng của thuật
toán:
Gọi điểm xuất phát là X, điểm đích cần đến là Y, thuất toán
Dijkstra sẽ lần lượt thực hiện như sau:
. 1.Thiết lập giá trị khoảng cách từ X đến với các
điểm: giá trị là 0 đối với X->X, là vô cùng X->K (K là một đỉnh nào đó).
. 2. Khởi tạo giá trị cờ (đã ghé thăm) của các đỉnh
là false.
3.Từ đỉnh C hiện tại, xem xét những đỉnh lân cận của
C, nếu giá trị của đỉnh lân cận lớn hơn giá trị của C cộng với cạnh nối giữa C
và điểm lân cận, ta thay thế giá trị của đỉnh lân cận bằng với giá trị của C cộng
với cạnh nối. (Lưu ý: C chính là X trong lần đi đầu tiên).
4.Nếu đỉnh C đã xem xét hết các lân cận, đánh dấu
cờ cho đỉnh C là true, và sẽ không quay lại tính giá trị của C lần nữa.
5.Nếu đỉnh Y (đỉnh đích) được đánh dấu cờ là true,
thì thuật toán kết thúc. Hoặc giá trị nhỏ nhất của các đỉnh chưa được dán cờ là
vô cùng thì thuật toán kết thúc, do không có đường đi tồn tại.
6.Tìm giá trị nhỏ nhất trong các đỉnh chưa được
gán cờ, và gán đỉnh đó thành đỉnh hiện tại cần xem xét lân cận, lặp lại bước 3.
Ứng dụng của thuật
toán:
Khi hướng đến mục tiêu giải quyết những bài toán về tìm kiếm
đường đi trên bản đồ địa lý, chẳng hạn như tìm kiểm đường đi trong thành phố,
những khái niệm đỉnh, cạnh của đồ thị được chuyển đổi như sau: những đỉnh của đồ
thị mô tả những giao lộ, nút giao thông, cạnh của đồ thị chính là đoạn đường nối
giữa 2 nút giao thông. Như vậy việc tìm kiếm đường đi từ 2 giao lộ chính là bài
toán tìm kiếm đường đi giữa 2 đỉnh của đồ thị.
Hiện thực thuật toán
Dijkstra với ngôn ngữ C++
Danh sách các hàm được dùng:
/* Đọc dữ liệu từ file
_IN_FILE lưu thành ma trận kề của đồ thị */
bool readFile();
/* Khởi tạo ma trận kề trước
khi đọc file */
void initMatrix();
/* Khởi tạo giá trị chuẩn bị
thuật toán Dijktra */
void initDijkstra();
/* Thực hiện thuật toán
Dijkstra */
bool doDijkstra();
/* Lấy giá trị nhỏ nhất của
khoảng cách từ điểm bắt đầu đến điểm hiện tại, bỏ qua các điểm đã ghé thăm */
int getIdOfMinDistance();
/* In ra đường đi ngắn nhất
tìm được */
void printShortestPath();In ra đường
đi ngắn nhất tìm được */
Các biến được dùng trong thuật toán:
/* Số đỉnh của đồ thị */
int numOfVertex;
/* Số cạnh của đồ thị */
int numOfEdge;
/* Đỉnh bắt đầu, đỉnh kết
thúc */
int sourceId, targetId;
/* Ma trận kề của đồ thị */
int matrix[20][20];
/* Mảng giá trị đường đi ngắn
nhất từ đỉnh xuất phát đến đỉnh có id tương ứng */
int distances[20];
/* Mảng đánh dấu đỉnh đã ghé
thăm */
bool visited[20];
/* Mảng truy vết đỉnh phía
trước đỉnh đã được đánh dấu */
int previous[20];
Đọc vào file dữ liệu với cấu trúc như sau:
·
Hàng đầu tiên: <số đỉnh> <số cạnh>
<điểm đầu> <điểm cuối>
·
Danh sách cách cạnh: <đỉnh x> <đỉnh
y> <trọng số nối x và y>
bool readFile() {
ifstream inFile(_IN_FILE);
// Kiểm tra file mở thành công
hay không
if (inFile.is_open()) {
// Đọc vào số đỉnh và số cạnh
của đồ thị, điểm bắt đầu và điểm kết thúc
inFile >> numOfVertex >> numOfEdge >> sourceId >> targetId;
// Khởi tạo ma trận
initMatrix();
// Lặp lại số cạnh, đọc vào
thông tin của cạnh với tham số như sau: đỉnh x, đỉnh y, cạnh x->y (y->x)
int x, y, dxy;
for (int i = 0; i < numOfEdge; i++) {
inFile >> x >> y >> dxy;
// Gán
giá trị cạnh xy yx cho ma trận kề.
matrix[x][y] = matrix[y][x] = dxy;
}
return true;
}
return false;
}
Khởi tạo ma trận kề, và các giá trị cần thiết
để bắt đầu thuật toán
void initMatrix() {
// Khởi tạo ma trận với giá
trị vô cùng ở các cạnh
int value;
for (int i = 0; i < numOfVertex; i++) {
for (int j = 0; j < numOfVertex; j++) {
// Khởi
tạo giá trị vô cùng tại cạnh j, i
value = INFINITY;
// Giá
trị 0 tại giá trị đường đi từ i->i
if (i == j) {
value = 0;
}
matrix[i][j] = value;
}
}
}
void initDijkstra() {
// Khởi tạo khoảng cách từ đỉnh
bắt đầu đến tất cả các đỉnh còn lại là vô cùng.
// Khởi tạo mảng đánh dấu đỉnh
đã được ghé thăm hay chưa
for (int i = 0; i < numOfVertex; i++) {
distances[i] = INFINITY;
visited[i] = false;
}
// Khởi tạo khoảng cách đến
đỉnh bắt đầu là 0.
distances[sourceId] = 0;
visited[sourceId] = false;
}
Hiện thực thuật toán:
int getIdOfMinDistance() {
int currentId, minDistance;
minDistance = INFINITY;
currentId = 0;
for (int i = 0; i < numOfVertex; i++) {
if ((!visited[i]) && (distances[i] < minDistance)) {
currentId = i;
}
}
return currentId;
}
bool doDijkstra() {
int currentId, int dxy;
while (true) {
// Tìm giá trị nhỏ nhất cả
mảng khoảng cách để tính điểm hiện tại.
currentId = getIdOfMinDistance();
// Kiểm tra giá trị của
currentId nếu giá trị là vô cùng thì thuật toán kết thúc, không tìm thấy đường đi.
if (distances[currentId] == INFINITY) {
return false;
}
else {
// Gán
đỉnh hiện tại đã ghé thăm
visited[currentId] = true;
// Nếu
đỉnh hiện tại chính là đỉnh đích cần đến thì kết thúc thuật toán
if (currentId == targetId) {
return true;
}
}
// Từ điểm hiện tại tiếp tục
loang tìm kiếm các đỉnh lân cận
for (int i = 0; i < numOfVertex; i++) {
// Nếu
tồn tại cạnh nối giữa currentId và i
dxy = matrix[currentId][i];
if ((dxy != INFINITY) && (currentId != i)) {
// Nếu
đỉnh i chưa ghé thăm và khoản cách từ current đến i nhỏ hơn khoảng cách hiện tại
của i.
if (distances[currentId] + dxy < distances[i]) {
// Thay gía trị mới cho i
distances[i] = distances[currentId] + dxy;
// Đỉnh trước i là current
previous[i] = currentId;
}
}
}
}
}
In ra kết quả tìm được:
void printShortestPath() {
int currentId = targetId;
while (true) {
cout << currentId << " ";
if (currentId == sourceId) {
return;
}
currentId = previous[currentId];
}
}
Kết luận:
Trên thực tế, bài toán tìm đường được gắn với một số tùy chọn
khác như: đường 1 chiều, biển báo,… tùy vào tình huống thực tế thuật toán
Dijkstra có thể được cài đặt bổ sung.
Bài viết trên đây là góc nhìn cá nhân tôi đối với thuật
toán, do đó sẽ còn rất nhiều thiếu sót, mong rằng quý bạn đọc sẽ góp ý thông để
tôi dần hoàn thiện hơn. Vui lòng liên hệ levohuutri@gmail.com.
Chúc sức khỏe.
Source code hoàn thiện: https://www.dropbox.com/s/n726juoqyrjnxk5/SourceDijkstra.cpp?dl=0
Sao source code hoàn thiện không vào được vậy nè :'(
Trả lờiXóa