Ở đây, mình có viết một chương trình tìm đường đi ngắn nhất bằng C#, dữ liệu test với đồ thị có 6 đỉnh và dữ liệu thật của một nút giao thông có 5011 đỉnh.
Trong đó, khi mình test với dữ liệu thật của một nút giao thông có 5011 đỉnh thì thời gian thực hiện ở mức chấp nhận được khi chỉ mất 36 mili giây để tìm được đường đi ngắn nhất.
Ta bắt đầu khởi tạo các mảng n phần tử: label, length, prev. Gán label[k] = 1, length[k] = -1 [inf], prev[k] = -1 với k chạy từ 0 -> n – 1. Gán length[first] = 0.
Chọn đỉnh v trong mảng sao cho length[k] là nhỏ nhất. Sau đó gán label[k] = 0 [Đã đánh dấu].
Tạo vòng lặp với biến chạy k, xét nếu label[k] = 1 [Chưa đánh dấu] và có đường đi từ v -> k: Nếu length[k] > length[v] + trọng số từ v -> k hoặc length[k] = inf, có nghĩa là nếu ta tìm được 1 đường từ v -> k là nhỏ nhất, hoặc là chưa tìm được đường nào ngắn nhất [inf] => Gán length[k] = length[v] + trọng số v -> k, prev[k] = v [Tạo vết chân đỉnh trước đó].
Nếu label[last] = 0 [Đã đánh dấu đỉnh đến], kết thúc vòng lặp. Nếu không thì quay lại bước 2.
VD: Ta có 1 đồ thị như sau
2. Viết và chạy thuật toán
Để đơn giản, trong phần này tôi dùng ma trận kề, và mỗi các đỉnh được đặt tên theo số thứ tự 0,1,2.
/**
- Trong nay, cac dinh khong co canh noi voi nhau se co khoang cach la -1
/
public int[] dijkstra[int[][] graph, int s]{
int [] dist = new int[graph.length];
for[int i = 0; i < graph.length; i++]{
dist[i] = Integer.MAX_VALUE;
}
dist[s] = 0;
int [] visit = new int[graph.length];
for[int i = 0; i < graph.length; i ]{
int v = closestVertice[graph[s], visit];
for[int j = 0; j < graph[v].length; j]{
if [graph[v][j] != -1]{ // neu co canh noi giua v va j
int currentDist = dist[v] + graph[v][j];
if [currentDist < dist[j]]{
dist[j] = currentDist;
}
}
}
}
return dist;
}
/*
- Chon ra dinh o gan s nhat va danh dau dinh do la da tham
- */
public int closestVertice[int[] adjacentVertices, int[] visit]{
int closest = -1;
int minDist = Integer.MAX_VALUE;
for[int i = 0; i < adjacentVertices.length; i ++]{
if [visit[i] == 0 && adjacentVertices[i] < minDist]{
closest = i;
minDist = adjacentVertices[i];
}
}
visit[closest] = 1;
return closest;
}
Output của thuật toán trên sẽ là:
Distance from '0' to '0':0
Distance from '0' to '1':2
Distance from '0' to '2':3
Distance from '0' to '3':4
Distance from '0' to '4':4
3.Đánh giá độ phức tạp
Độ phức tạp của thuật toán trên sẽ là O[V2].
Nếu ta sử dụng một hàng đợi ưu tiên [priority queue], ví dụ như Binary heap, và sử dụng danh sách kề thì độ phức tạp của thuật toán sẽ bị giảm xuống còn O[[V+E]∗logV].
Nguyên nhân là, với danh sách kề, thời gian để duyệt các cạnh và các đỉnh sẽ là O[E+V] thay vì O[V2] như ma trận kề. Ngoài ra, với binary heap, việc tìm đỉnh gần nhất ở
closestVertice[graph[s], visit];
sẽ chỉ còn O[1] thay vì O[V]. Vì thế ta cần nhập khoảng cách tới các đỉnh xung quanh vào binary heap bằng cách bỏ các đỉnh đó ra khỏi heap rồi thêm lại, cái này mất O[logV].
Vậy cuối cùng độ phức tạp sẽ là O[[V+E]∗logV].
Trên đây là bài viết về "Tìm đường ngắn nhất bằng thuật toán Dijkstra". Tuỳ theo từng yêu cầu cụ thể mà bạn có thể lựa chọn cách làm hợp lý.
Các bài toán về tìm đường đi ngắn nhất và biến tướng của nó luôn xuất hiện rất nhiều trong các cuộc thi lập trình thi đấu bởi sự đa dạng trong cách đưa ra đề bài và sử dụng. Một trong những thuật toán tìm đường đi ngắn nhất được sử dụng phổ biến đó là thuật toán Dijkstra.
Theo Wikipedia, 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 19561956 và ấn bản năm 19591959, 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 thường được sử dụng trong định tuyến với một chương trình con trong các thuật toán đồ thị hay trong công nghệ Hệ thống định vị toàn cầu [GPS].
Ví dụ: Chúng ta dùng các đỉnh của đồ thị để biểu diễn các thành phố và các cạnh để biểu diễn các đường nối giữa chúng. Khi đó trọng số các cạnh có thể xem như độ dài của các con đường [do đó không âm]. Chúng ta cần di chuyển từ thành phố ss đến thành phố tt. Thuật toán Dijkstra sẽ giúp chỉ ra đường đi ngắn nhất có thể đi.
Trọng số không âm của các cạnh của đồ thị mang tính tổng quát hơn khoảng cách hình học giữa hai đỉnh đầu mút của chúng. Ví dụ, với 3 đỉnh A,B,CA, B, C đường đi A−B−CA-B-C có thể ngắn hơn so với đường đi trực tiếp A−CA-C.
Kĩ thuật
Mô tả thuật toán
Để dễ hình dung cách hoạt động của thuật toán, ta xét ví dụ sau.
Cho đồ thị như hình dưới:
Nguồn ảnh: //www.codingame.com
Hãy tìm đường đi ngắn nhất giữa đỉnh CC và các đỉnh còn lại trong đồ thị.
Ta sẽ áp dụng thuật toán Dijkstra cho đồ thị trên, hãy nghiên cứu thật kĩ từng công đoạn một vì nếu chỉ bỏ qua một chi tiết nhỏ ta sẽ không thể hiểu thuật toán được:
- Trong toàn bộ quá trình thực thi thuật toán, ta sẽ đánh dấu tất cả các đỉnh bằng khoảng cách nhỏ nhất từ đỉnh CC tới các đỉnh đó. Với đỉnh CC, khoảng cách sẽ là 00 [tất nhiên rồi ]. Với các đỉnh còn lại, ban đầu chưa biết khoảng cách nhỏ nhất nên ta sẽ đánh dấu mỗi đỉnh bằng giá trị vô cùng [∞].
Chúng ta cũng đánh dấu đỉnh hiện tại đang xét [ban đầu là đỉnh nguồn CC]. Ở đồ thị trên, ta đánh dấu bằng một chấm đỏ ở đỉnh CC [đỉnh hiện tại đang xét].
- Okay! Giờ chúng ta kiểm tra các đỉnh kề với đỉnh hiên tại đang xét [đỉnh CC - current node] đó là đỉnh A, B, D [không cần theo thứ tự cụ thể]. Hãy bắt đầu với đỉnh BB. Tớ sẽ lấy giá trị dùng đánh dấu ở đỉnh CC [giá trị 00] cộng với trọng số của cạnh nối đỉnh đang xét [đỉnh CC] với đỉnh BB [trong trường hợp này là 7], ta được 0+7=70 + 7 = 7. Oke roài, sau đó ta sẽ so sánh giá trị vừa tính được với giá trị dùng đánh dấu ở đỉnh BB [vô cùng]. Ta sẽ đánh dấu đỉnh BB nhận giá trị nhỏ hơn là 77 [77 nhỏ hơn vô cùng].
Đỉnh BB đã xong, giờ ta kiểm tra đỉnh kề AA. Ta cộng 00 [giá trị dùng đánh dấu ở đỉnh CC] với 11 [trọng số của cạnh nối đỉnh CC với đỉnh AA] và được 0+1=10 + 1 = 1. Dễ thấy giá trị 11 nhỏ hơn vô cùng [giá trị dùng đánh dấu ở đỉnh AA]. Do đó ta sẽ đánh dấu đỉnh AA nhận giá trị 11.
Tương tự với đỉnh DD:
Yay! Ta đã xét xong các đỉnh kề với đỉnh đang xét [đỉnh CC]. Tớ sẽ đánh một dấu tick ở đỉnh CC để thể hiện rằng các đỉnh kề nó đã được xét xong.
- Giờ ta sẽ xét sang một đỉnh mới [gọi là đỉnh hiện tại đang xét - current node]. Đỉnh này phải thỏa mãn điều kiện là chưa được xét và được đánh dấu với giá trị nhỏ nhất. Đó là đỉnh AA [bạn đọc kiểm tra lại hai điều kiện trên với đỉnh AA nhé ]. Tương tự như đỉnh CC, ta sẽ đánh dấu đỉnh AA bằng một dấu chấm đỏ.
Okay, bây giờ ta lặp lại thuật toán như đã làm với đỉnh CC. Chúng ta kiểm tra các đỉnh kề với đỉnh AA [Current node], nhớ rằng không kiểm tra những đỉnh đã xét rồi [đỉnh CC]. Vậy là ta chỉ cần kiểm tra đỉnh BB.
Với BB, Ta cộng 11 [giá trị được đánh dấu ở đỉnh AA] với 33 [trọng số của cạnh nối đỉnh AA với đỉnh BB] và được 44. Vì 447 > 4, vẫn giữ 44 là giá trị đánh dấu cho đỉnh BB. Với EE, ta có 2+7=92 + 7 = 9 [9SP[s,v]dist[v]> SP[s, v] khi vv được xóa khỏi hàng đợi ưu tiên QQ. Cụ thể, gọi ff là đỉnh đầu tiên được xóa khỏi QQ có tính chất trên. Khi đó, Pf=⟨s=u1,u2,...,uh=f⟩P_f = \langle s = u_1, u_2, ..., u_h = f \rangle là chuỗi các đỉnh trên đường đi ngắn nhất từ ss đến ff, trong đó hh là số đỉnh trên đường đi ngắn nhất này.
Xét vòng lặp while mà ta dequeue ff từ QQ. Coi một đỉnh vv được đánh dấu nếu tại thời điểm này vv đã bị xóa khỏi QQ. Gọi uku_k là đỉnh đầu tiên trong PfP_f không được đánh dấu, tức là mọi đỉnh trong đường dẫn con ⟨hs,u2,...,uk−1⟩\langle h_s, u_2, ..., u_{k − 1} \rangle được đánh dấu và do đó đã bị xóa khỏi QQ.
Trong phần còn lại của chứng minh, ta sử dụng hai dữ kiện quan trọng sau:
Dữ kiện 1: Vì ff là đỉnh đầu tiên bị xóa khỏi QQ nên tại thời điểm loại bỏ nó [ở cuối thuật toán], ta có SP[s,f]