1. Thuật toán Dijkstra
Cho G=(X,E) là một đồ thị có trọng không âm gồm n đỉnh. Thuật toán Dijkstra được dùng để tìm
đường đi ngắn nhất từ đỉnh i đến j cho trước.
Gọi L là ma trận trọng lượng (với qui ước Lhk = +∞ nếu không có cạnh nối từ đỉnh h đến đỉnh k). Ta sử dụng thêm hai mảng để lưu vết của quá trình tìm đường đi:
- Dodai[…] : lưu độ dài từ đỉnh đầu i đến các đỉnh trong đồ thị.
- Nhan[…] : lưu đỉnh liền trước nó trên đường đi.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Bước 1: Gán T:= X và gán các nhãn: Dodai[i] = 0; Dodai[k] = +∞ vớik X \{i}; Nhan[k] = -1; k X ; Bước 2: Nếu j T thì dừng và giá trị Dodai[j] là độ dài đường đi ngắn nhất từ i đến j và Nhan[j] lưu đỉ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: 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; Nhan[k] = v; Cuối nếu Cuối với mọi Trở về bước 2 |
2. Thuật toán Floyd
Cho G=(X, E) là một đồ thị có trọng không âm gồm n đỉnh. Thuật toán Floyd được dùng để tìm
đường đi ngắn nhất giữa tất cả cặp đỉnh bất kỳ của một đồ thị G.
Gọi L là ma trận trọng lượng (với qui ước Lhk = 0 nếu không có cạnh nối từ đỉnh h đến đỉnh k). Ta sử dụng thêm một ma trận nxn để lưu vết của quá trình tìm đường đi:
– sau_nut1[i,j] : lưu chỉ số của đỉnh ngay sau i trên đường đi từ i đến j.
1 2 3 4 5 6 7 8 9 10 11 12 |
Bước 1: (khởi tạo) u,v X : Nếu Luv > 0 thì sau_nut1[u,v] = v; Nếu không sau_nut1[u,v] = -1; Cuối nếu Bước 2: Với mỗi đỉnh trung gian k, tìm cặp i, j nào thỏa mãn L[i,j] = 0 hoặc L[i, j] > L[i, k] + L[k, j] Nếu thỏa mãn thì L[i,j] = L[i,k] + L[k,j]; sau_nut1[i,j] = sau_nut1[i,k]; Cuối nếu Cuối với mọi k, i, j |
Đỉnh k được gọi là trung gian của i, j nếu nó có đường đi từ i→k và k→j.Chú ý:
- Khi thuật toán kết thúc, nếu Lij = 0 thì không tồn tại đường đi từ i đến j, nếu ngược lại thì Lij là độ dài đường đi ngắn nhất.
- Trong cách làm ở trên, việc xuất ra đường đi chỉ cần duyệt một khoảng từ j→k có đỉnh trung gian hay không vì từ i→k không có đỉnh trung gian nào.
- Ta có thể không cần khởi tạo ma trận lưu chỉ số sau_nut1 như ở trên (set bằng 0). Như vậy trong bước 2, chỉ lưu giá trị trung gian đơn giản như sau: sau_nut1[i,j] = k . Tuy nhiên, việc xuất ra đường đi từ i đến j chúng ta phải tiến hành duyệt hai khoảng i→k và k→j để kiểm tra xem có đỉnh nào làm trung gian bên trong hai khoảng này nữa không.
3. Thuật toán Bellman
Khác với thuật toán Dijkstra và Floyd, Bellman giải quyết được cả trường hợp đồ thị có cạnh âm. Thuật toán còn phát hiện được cả trường hợp đồ thị có chu trình âm. Từ một đỉnh x cho trước, thuật toán Bellman cho phép xác định đường đi ngắn nhất đến tất cả các đỉnh trong đồ thị.
Nhận xét rằng đường đi ngắn nhất (không chứa chu trình âm) từ một đỉnh x đến một đỉnh y trong một đồ thị có n đỉnh chi đi qua tối đa n đỉnh. Thuật toán Bellman bước 0 bắt đầu với giả thiết rằng từ đỉnh x, nếu đi qua tối đa là 1 đỉnh (kể cả đỉnh xuất phát) ta sẽ chỉ đến được đỉnh x với chi phí là 0. Bước 1, nếu đi qua tối đa là 2 đỉnh, ta sẽ đến được các đỉnh trong bước 0 và các đỉnh i (sao cho có cung nối trực tiếp từ một đỉnh j thuộc bước 0 đến i)…
Trong quá trình mở rộng mỗi bước, tại mỗi đỉnh đã đi đến được i đã, ta sẽ lưu lại đỉnh cha thỏa mãn điều kiện đường đi ngắn nhất đến i. Sau đây là một ví dụ minh họa cho thuật toán Bellman.
Cho trước đồ thị có hướng G (có thể chứa cạnh âm). Tìm đường đi xuất phát từ đỉnh x đến tất cả các đỉnh trong đồ thị.
Bước 0: step = 0
mincost[step][i] = ∞, i ≠ x mincost[step][x] = 0 |
Để có thể lưu lại đường đi, ngắn nhất, ta cần thêm mảng previous để lưu lại đường đi
previous[step][x] = x (bằng chính nó) |
Bước 2: step++;
nếu step ≥ n thì dừng thuật toán(*) mincost[step][i] = min( mincost[step-1][i], min({mincost[step-1][j]+a[j][i]}) ), i,j Với a[j][i] == ∞ nếu không có cung nối |
previous[step][i] =:
· j nếu đường đi ngắn nhất đi qua trung gian j rồi đến i · i nếu đường đi đến i đã tối ưu |
Bước 3: Nếu
mincost[step][i] == mincost[step-1][i], i mọi đường đi đã được tối ưu, dừng thuật toán. Ngược lại, quay lại bước 2. |
(*): Nếu như chúng ta đã đi qua đủ n đỉnh nhưng vẫn chưa tối ưu được đường đi, ta có thể kết luận được đồ thị có chu trình âm.
Không như khi cài đặt các thuật toán Dijkstra, Floy, do Bellman chấp nhận cạnh âm, việc sử dụng trị -1 không còn đúng nữa. Tạm thời, ta có thể sử dụng trị MAXINT (32767) cho giá trị VOCUC, vì nếu như chi phí đạt đến ngưỡng này, có thể xem như tràn số.
1 2 3 4 5 6 7 8 9 |
step = 0; for (i…) { mincost[step][i] = VOCUC; //dùng 32767 cho trị vô cực previous[step][i] = i; } mincost[step][x] = 0; |
Chú ý rằng để có thể kết luận được đồ thị có chu trình âm hay không, ta cần chạy đến bước thứ n (nghĩa là đi qua tối đa n+1 đỉnh). Do đó, cấu trúc dữ liệu để lưu cũng cần lưu ý khi khai báo.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
bSuccess = false; for (step=1; step<=n; step++) // (dùng <=n thay vì <n) { for (i…) { mincost[step][i] = mincost[step-1][i] previous[step][i] = previous[step-1][i] // tìm các đỉnh j có đường nối từ j --> i // và chi phí bước step-1 của j khác ∞ for (j…) if (… && …) { // cập nhật lại nếu chi phí bước step của i là ∞ // hoặc chi phí đi qua j: mincost[step-1][j]+a[j][i] // tối ưu hơn if (… || …) { // cập nhật lại chi phí và lưu đỉnh cha … } } } // so sánh mincost[step] với mincost[step-1], nếu bằng nhau // kết thúc thành công int bSame = true; for (i…) if (mincost[step][i] != mincost[step-1][i]) { bSame = false; break; } // đã giống nhau, đường đi đã tối ưu if (bSame) break; } |
Leave a Reply