Giải Thuật Và Lập Trình: §8. Bài Toán đường đi Ngắn Nhất | V1Study

8.1. Đồ thị có trọng số

Đồ thị mà mỗi cạnh của nó được gán cho tương ứng với một số (nguyên hoặc thực) được gọi là đồ thị có trọng số. Số gán cho mỗi cạnh của đồ thị được gọi là trọng số của cạnh. Tương tự như đồ thị không trọng số, có nhiều cách biểu diễn đồ thị có trọng số trong máy tính. Đối với đơn đồ thị thì cách dễ dùng nhất là sử dụng ma trận trọng số:

Giả sử đồ thị G = (V, E) có n đỉnh. Ta sẽ dựng ma trận vuông C kích thước n x n. Ở đây:

Nếu (u, v) ∈ E thì C[u, v] = trọng số của cạnh (u, v)

Nếu (u, v) ∉ E thì tuỳ theo trường hợp cụ thể, C[u, v] được gán một giá trị nào đó để có thể nhận biết được (u, v) không phải là cạnh (Chẳng hạn có thể gán bằng +∞, hay bằng 0, bằng -∞ v.v...)

Quy ước c[v, v] = 0 với mọi đỉnh v.

Đường đi, chu trình trong đồ thị có trọng số cũng được định nghĩa giống như trong trường hợp không trọng số, chỉ có khác là độ dài đường đi không phải tính bằng số cạnh đi qua, mà được tính bằng tổng trọng số của các cạnh đi qua.

8.2. Bài toán đường đi ngắn nhất

Trong các ứng dụng thực tế, chẳng hạn trong mạng lưới giao thông đường bộ, đường thuỷ hoặc đường không. Người ta không chỉ quan tâm đến việc tìm đường đi giữa hai địa điểm mà còn phải lựa chọn một hành trình tiết kiệm nhất (theo tiêu chuẩn không gian, thời gian hay chi phí). Khi đó phát sinh yêu cầu tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị. Bài toán đó phát biểu dưới dạng tổng quát như sau: Cho đồ thị có trọng số G = (V, E), hãy tìm một đường đi ngắn nhất từ đỉnh xuất phát S ∈ V đến đỉnh đích F ∈ V. Độ dài của đường đi này ta sẽ ký hiệu là d[S, F] và gọi là khoảng cách từ S đến F. Nếu như không tồn tại đường đi từ S tới F thì ta sẽ đặt khoảng cách đó = +∞.

Nếu như đồ thị có chu trình âm (chu trình với độ dài âm) thì khoảng cách giữa một số cặp đỉnh nào đó có thể không xác định, bởi vì bằng cách đi vòng theo chu trình này một số lần đủ lớn, ta có thể chỉ ra đường đi giữa hai đỉnh nào đó trong chu trình này nhỏ hơn bất kỳ một số cho trước nào.

Trong trường hợp như vậy, có thể đặt vấn đề tìm đường đi cơ bản (đường đi không có đỉnh lặp lại) ngắn nhất. Vấn đề đó là một vấn đề hết sức phức tạp mà ta sẽ không bàn tới ở đây.

Nếu như đồ thị không có chu trình âm thì ta có thể chứng minh được rằng một trong những đường đi ngắn nhất là đường đi cơ bản. Và nếu như biết được khoảng cách từ S tới tất cả những đỉnh khác thì đường đi ngắn nhất từ S tới F có thể tìm được một cách dễ dàng qua thuật toán sau:

Gọi c[u, v] là trọng số của cạnh [u, v]. Qui ước c[v, v] = 0 với mọi v ∈ V và c[u, v] = +∞ nếu như (u, v) ∉ E. Đặt d[S, v] là khoảng cách từ S tới v. Để tìm đường đi từ S tới F, ta có thể nhận thấy rằng luôn tồn tại đỉnh F1 ≠ F sao cho:

d[S, F] = d[S, F1] + c[F1, F]

(Độ dài đường đi ngắn nhất S->F = Độ dài đường đi ngắn nhất S->F1 + Chi phí đi từ F1 tới F)

Đỉnh F1 đó là đỉnh liền trước F trong đường đi ngắn nhất từ S tới F. Nếu F1≡S thì đường đi ngắn nhất là đường đi trực tiếp theo cung (S, F). Nếu không thì vấn đề trở thành tìm đường đi ngắn nhất từ S tới F1. Và ta lại tìm được một đỉnh F2 khác F và F1 để:

d[S, F1] = d[S, F2] + c[F2, F1]

Cứ tiếp tục như vậy, sau một số hữu hạn bước, ta suy ra rằng dãy F, F1, F2, ... không chứa đỉnh lặp lại và kết thúc ở S. Lật ngược thứ tự dãy cho ta đường đi ngắn nhất từ S tới F.

Tuy nhiên, người ta thường không sử dụng phương pháp này mà sẽ kết hợp lưu vết đường đi ngay trong quá trình tìm kiếm.

Dưới đây ta sẽ xét một số thuật toán tìm đường đi ngắn nhất từ đỉnh S tới đỉnh F trên đơn đồ thị có hướng G = (V, E) có n đỉnh và m cung. Trong trường hợp đơn đồ thị vô hướng với trọng số không âm, bài toán tìm đường đi ngắn nhất có thể dẫn về bài toán trên đồ thị có hướng bằng cách thay mỗi cạnh của nó bằng hai cung có hướng ngược chiều nhau. Lưu ý rằng các thuật toán dưới đây sẽ luôn luôn tìm được đường đi ngắn nhất là đường đi cơ bản.

Input: file văn bản MINPATH.INP

• Dòng 1: Chứa số đỉnh n ( ≤ 100), số cung m của đồ thị, đỉnh xuất phát S, đỉnh đích F cách nhau ít nhất 1 dấu cách

• m dòng tiếp theo, mỗi dòng có dạng ba số u, v, c[u, v] cách nhau ít nhất 1 dấu cách, thể hiện (u, v) là một cung ∈ E và trọng số của cung đó là c[u,v] (c[u, v] là số nguyên có giá trị tuyệt đối ≤ 100)

Output: file văn bản MINPATH.OUT ghi đường đi ngắn nhất từ S tới F và độ dài đường đi đó.

8.3. Trường hợp đồ thị không có chu trình âm - Thuật toán Ford Bellman

Thuật toán Ford-Bellman có thể phát biểu rất đơn giản:

Với đỉnh xuất phát S. Gọi d[v] là khoảng cách từ S tới v với các giá trị khởi tạo là:

• d[S] = 0

• d[v] = +∞ nếu v ≠ S

Sau đó ta tối ưu hoá dần các d[v] như sau: Xét mọi cặp đỉnh u, v của đồ thị, nếu có một cặp đỉnh u, v mà d[v] > d[u]+ c[u, v] thì ta đặt lại d[v] := d[u] + c[u, v]. Tức là nếu độ dài đường đi từ S tới v lại lớn hơn tổng độ dài đường đi từ S tới u cộng với chi phí đi từ u tới v thì ta sẽ huỷ bỏ đường đi từ S tới v đang có và coi đường đi từ S tới v chính là đường đi từ S tới u sau đó đi tiếp từ u tới v.

Chú ý rằng ta đặt c[u, v] = +∞ nếu (u, v) không là cung. Thuật toán sẽ kết thúc khi không thể tối ưu thêm bất kỳ một nhãn d[v] nào nữa.

Tính dúng của thuật toán:

Tại bước khởi tạo thì mỗi d[v] chính là độ dài ngắn nhất của đường đi từ S tới v qua không quá 0 cạnh.

Giả sử khi bắt đầu bước lặp thứ i (i ≥ 1), d[v] đã bằng độ dài đường đi ngắn nhất từ S tới v qua không quá i - 1 cạnh. Do tính chất: đường đi từ S tới v qua không quá i cạnh sẽ phải thành lập bằng cách: lấy một đường đi từ S tới một đỉnh u nào đó qua không quá i - 1 cạnh, rồi đi tiếp tới v bằng cung (u, v), nên độ dài đường đi ngắn nhất từ S tới v qua không quá i cạnh sẽ được tính bằng giá trị nhỏ nhất trong các giá trị: (Nguyên lý tối ưu Bellman).

Độ dài đường đi ngắn nhất từ S tới v qua không quá i - 1 cạnh

Độ dài đường đi ngắn nhất từ S tới u qua không quá i - 1 cạnh cộng với trọng số cạnh (u, v) (∀u)

Vì vậy, sau bước lặp tối ưu các d[v] bằng công thức d[v]bước i = min(d[v]bước i-1, d[u]bước i-1+ c[u, v]) (∀u) thì các d[v] sẽ bằng độ dài đường đi ngắn nhất từ S tới v qua không quá i cạnh.

Sau bước lặp tối ưu thứ n - 1, ta có d[v] = độ dài đường đi ngắn nhất từ S tới v qua không quá n - 1 cạnh. Vì đồ thị không có chu trình âm nên sẽ có một đường đi ngắn nhất từ S tới v là đường đi cơ bản (qua không quá n - 1 cạnh). Tức là d[v] sẽ là độ dài đường đi ngắn nhất từ S tới v.

Vậy thì số bước lặp tối ưu hoá sẽ không quá n - 1 bước.

Trong khi cài đặt chương trình, nếu mỗi bước lặp được mô tả dưới dạng:

for u := 1 to n do for v := 1 to n do d[v] := min(d[v], d[u] + c[u, v]);

Do sự tối ưu bắc cầu (dùng d[u] tối ưu d[v] rồi lại có thể dùng d[v] tối ưu d[w] nữa...) chỉ làm tốc độ tối ưu nhãn d[v] tăng nhanh hơn nên số bước lặp tối ưu nhãn vẫn sẽ không quá n - 1 bước.

P_4_08_1.PAS * Thuật toán Ford-Bellman program Shortest_Path_by_Ford_Bellman; const InputFile = 'MINPATH.INP'; OutputFile = 'MINPATH.OUT'; max = 100; maxC = 10000; var c: array[1..max, 1..max] of Integer; d: array[1..max] of Integer; Trace: array[1..max] of Integer; n, S, F: Integer; procedure LoadGraph; {Nhập đồ thị, đồ thị không được có chu trình âm} var i, m, u, v: Integer; fi: Text; begin Assign(fi, InputFile); Reset(fi); ReadLn(fi, n, m, S, F); {Những cạnh không có trong đồ thị được gán trọng số +∞} for u := 1 to n do for v := 1 to n do if u = v then c[u, v] := 0 else c[u, v] := maxC; for i := 1 to m do ReadLn(fi, u, v, c[u, v]); Close(fi); end; procedure Init; {Khởi tạo} var i: Integer; begin for i := 1 to n do d[i] := MaxC; d[S] := 0; end; procedure Ford_Bellman; {Thuật toán Ford-Bellman} var Stop: Boolean; u, v, CountLoop: Integer; begin for CountLoop := 1 to n - 1 do begin Stop := True; for u := 1 to n do for v := 1 to n do if d[v] > d[u] + c[u, v] then {Nếu ∃u, v thoả mãn d[v] > d[u] + c[u, v] thì tối ưu lại d[v]} begin d[v] := d[u] + c[u, v]; Trace[v] := u; {Lưu vết đường đi} Stop := False; end; if Stop then Break; end; {Thuật toán kết thúc khi không sửa nhãn các d[v] được nữa hoặc đã lặp đủ n - 1 lần } end; procedure PrintResult; {In đường đi từ S tới F} var fo: Text; begin Assign(fo, OutputFile); Rewrite(fo); if d[F] = maxC then {Nếu d[F] vẫn là +∞ thì tức là không có đường} WriteLn(fo, 'Path from ', S, ' to ', F, ' not found') else {Truy vết tìm đường đi} begin WriteLn(fo, 'Distance from ', S, ' to ', F, ': ', d[F]); while F <> S do begin Write(fo, F, '<-'); F := Trace[F]; end; WriteLn(fo, S); end; Close(fo); end; begin LoadGraph; Init; Ford_Bellman; PrintResult; end.

8.4. Trường hợp trọng số trên các cung không âm - Thuật toán Dijkstra

Trong trường hợp trọng số trên các cung không âm, thuật toán do Dijkstra đề xuất dưới đây hoạt động hiệu quả hơn nhiều so với thuật toán Ford-Bellman. Ta hãy xem trong trường hợp này, thuật toán Ford-Bellman thiếu hiệu quả ở chỗ nào:

Với đỉnh v ∈ V, Gọi d[v] là độ dài đường đi ngắn nhất từ S tới v. Thuật toán Ford-Bellman khởi gán d[S] = 0 và d[v] = +∞ với ∀v ≠ S, sau đó tối ưu hoá dần các nhãn d[v] bằng cách sửa nhãn theo công thức: d[v] := min(d[v], d[u] + c[u, v]) với ∀u, v ∈ V. Như vậy nếu như ta dùng đỉnh u sửa nhãn đỉnh v, sau đó nếu ta lại tối ưu được d[u] thêm nữa thì ta cũng phải sửa lại nhãn d[v] dẫn tới việc d[v] có thể phải chỉnh đi chỉnh lại rất nhiều lần. Vậy nên chăng, tại mỗi bước không phải ta xét mọi cặp đỉnh (u, v) để dùng đỉnh u sửa nhãn đỉnh v mà sẽ chọn đỉnh u là đỉnh mà không thể tối ưu nhãn d[u] thêm được nữa.

Thuật toán Dijkstra (E.Dijkstra - 1959) có thể mô tả như sau:

Bước 1: Khởi tạo

Với đỉnh v ∈ V, gọi nhãn d[v] là độ dài đường đi ngắn nhất từ S tới v. Ta sẽ tính các d[v]. Ban đầu d[v] được khởi gán như trong thuật toán Ford-Bellman (d[S] = 0 và d[v] = ∞ với ∀v ≠ S). Nhãn của mỗi đỉnh có hai trạng thái tự do hay cố định, nhãn tự do có nghĩa là có thể còn tối ưu hơn được nữa và nhãn cố định tức là d[v] đã bằng độ dài đường đi ngắn nhất từ S tới v nên không thể tối ưu thêm.

Để làm điều này ta có thể sử dụng kỹ thuật đánh dấu: Free[v] = TRUE hay FALSE tuỳ theo d[v] tự do hay cố định. Ban đầu các nhãn đều tự do.

Bước 2: Lặp

Bước lặp gồm có hai thao tác:

1. Cố định nhãn: Chọn trong các đỉnh có nhãn tự do, lấy ra đỉnh u là đỉnh có d[u] nhỏ nhất, và cố định nhãn đỉnh u.

2. Sửa nhãn: Dùng đỉnh u, xét tất cả những đỉnh v và sửa lại các d[v] theo công thức:

d[v] := min(d[v], d[u] + c[u, v])

Bước lặp sẽ kết thúc khi mà đỉnh đích F được cố định nhãn (tìm được đường đi ngắn nhất từ S tới F); hoặc tại thao tác cố định nhãn, tất cả các đỉnh tự do đều có nhãn là +∞ (không tồn tại đường đi).

Có thể đặt câu hỏi, ở thao tác 1, tại sao đỉnh u như vậy được cố định nhãn, giả sử d[u] còn có thể tối ưu thêm được nữa thì tất phải có một đỉnh t mang nhãn tự do sao cho d[u] > d[t] + c[t, u]. Do trọng số c[t, u] không âm nên d[u] > d[t], trái với cách chọn d[u] là nhỏ nhất. Tất nhiên trong lần lặp đầu tiên thì S là đỉnh được cố định nhãn do d[S] = 0.

Bước 3: Kết hợp với việc lưu vết đường đi trên từng bước sửa nhãn, thông báo đường đi ngắn nhất tìm được hoặc cho biết không tồn tại đường đi (d[F] = +∞).

P_4_08_2.PAS * Thuật toán Dijkstra program Shortest_Path_by_Dijkstra; const InputFile = 'MINPATH.INP'; OutputFile = 'MINPATH.OUT'; max = 100; maxC = 10000; var c: array[1..max, 1..max] of Integer; d: array[1..max] of Integer; Trace: array[1..max] of Integer; Free: array[1..max] of Boolean; n, S, F: Integer; procedure LoadGraph; {Nhập đồ thị, trọng số các cung phải là số không âm} var i, m, u, v: Integer; fi: Text; begin Assign(fi, InputFile); Reset(fi); ReadLn(fi, n, m, S, F); for u := 1 to n do for v := 1 to n do if u = v then c[u, v] := 0 else c[u, v] := maxC; for i := 1 to m do ReadLn(fi, u, v, c[u, v]); Close(fi); end; procedure Init; {Khởi tạo các nhãn d[v], các đỉnh đều được coi là tự do} var i: Integer; begin for i := 1 to n do d[i] := MaxC; d[S] := 0; FillChar(Free, SizeOf(Free), True); end; procedure Dijkstra; {Thuật toán Dijkstra} var i, u, v: Integer; min: Integer; begin repeat {Tìm trong các đỉnh có nhãn tự do ra đỉnh u có d[u] nhỏ nhất} u := 0; min := maxC; for i := 1 to n do if Free[i] and (d[i] < min) then begin min := d[i]; u := i; end; {Thuật toán sẽ kết thúc khi các đỉnh tự do đều có nhãn + hoặc đã chọn đến đỉnh F} if (u = 0) or (u = F) then Break; {Cố định nhãn đỉnh u} Free[u] := False; {Dùng đỉnh u tối ưu nhãn những đỉnh tự do kề với u} for v := 1 to n do if Free[v] and (d[v] > d[u] + c[u, v]) then begin d[v] := d[u] + c[u, v]; Trace[v] := u; end; until False; end; procedure PrintResult; {In đường đi từ S tới F} var fo: Text; begin Assign(fo, OutputFile); Rewrite(fo); if d[F] = maxC then WriteLn(fo, 'Path from ', S, ' to ', F, ' not found') else begin WriteLn(fo, 'Distance from ', S, ' to ', F, ': ', d[F]); while F <> S do begin Write(fo, F, '<-'); F := Trace[F]; end; WriteLn(fo, S); end; Close(fo); end; begin LoadGraph; Init; Dijkstra; PrintResult; end.

8.5. Thuật toán Dijkstra và cấu trúc Heap

Nếu đồ thị có nhiều đỉnh, ít cạnh, ta có thể sử dụng danh sách kề kèm trọng số để biểu diễn đồ thị, tuy nhiên tốc độ của thuật toán DIJKSTRA vẫn khá chậm vì trong trường hợp xấu nhất, nó cần n lần cố định nhãn và mỗi lần tìm đỉnh để cố định nhãn sẽ mất một đoạn chương trình với độ phức tạp O(n). Để tăng tốc độ, người ta

thường sử dụng cấu trúc dữ liệu Heap để lưu các đỉnh chưa cố định nhãn. Heap ở đây là một cây nhị phân hoàn chỉnh thoả mãn: Nếu u là đỉnh lưu ở nút cha và v là

đỉnh lưu ở nút con thì d[u] ≤ d[v]. (Đỉnh r lưu ở gốc Heap là đỉnh có d[r] nhỏ nhất).

Tại mỗi bước lặp của thuật toán Dijkstra có hai thao tác: Tìm đỉnh cố định nhãn và Sửa nhãn.

Với mỗi đỉnh v, gọi Pos[v] là vị trí đỉnh v trong Heap, quy ước Pos[v] = 0 nếu v chưa bị đẩy vào Heap. Mỗi lần có thao tác sửa đổi vị trí các đỉnh trên cấu trúc Heap, ta lưu ý cập nhập lại mảng Pos này.

Thao tác tìm đỉnh cố định nhãn sẽ lấy đỉnh lưu ở gốc Heap, cố định nhãn, đưa phần tử cuối Heap vào thế chỗ và thực hiện việc vun đống (Adjust).

Thao tác sửa nhãn, sẽ duyệt danh sách kề của đỉnh vừa cố định nhãn và sửa nhãn những đỉnh tự do kề với đỉnh này, mỗi lần sửa nhãn một đỉnh nào đó, ta xác định đỉnh này nằm ở đâu trong Heap (dựa vào mảng Pos) và thực hiện việc chuyển đỉnh đó lên (UpHeap) phía gốc Heap nếu cần để bảo toàn cấu trúc Heap.

Cài đặt dưới đây có Input/Output giống như trên nhưng có thể thực hiện trên đồ thị 5000 đỉnh, 10000 cạnh, trọng số mỗi cạnh ≤ 10000.

P_4_08_3.PAS * Thuật toán Dijkstra và cấu trúc Heap program Shortest_Path_by_Dijkstra_and_Heap; const InputFile = 'MINPATH.INP'; OutputFile = 'MINPATH.OUT'; max = 5000; maxE = 10000; maxC = 1000000000; type TAdj = array[1..maxE] of Integer; TAdjCost = array[1..maxE] of LongInt; THeader = array[1..max + 1] of Integer; var adj: ^TAdj; {Danh sách kề dạng mảng} adjCost: ^TAdjCost; {Kèm trọng số} h: ^THeader; {Mảng đánh dấu các đoạn trong mảng adj^ chứa danh sách kề} d: array[1..max] of LongInt; Trace: array[1..max] of Integer; Free: array[1..max] of Boolean; heap: array[1..max] of Integer; {heap[i] = đỉnh lưu tại nút i của heap} Pos: array[1..max] of Integer; {pos[v] = vị trí của nút v trong heap (tức là pos[heap[i]] = i)} n, S, F, nHeap: Integer; procedure LoadGraph; {Nhập dữ liệu} var i, m, u, v, c: Integer; fi: Text; begin {Đọc file lần 1, để xác định các đoạn} Assign(fi, InputFile); Reset(fi); ReadLn(fi, n, m, S, F); New(h); New(adj); New(adjCost); {Phép đếm phân phối (Distribution Counting)} FillChar(h^, SizeOf(h^), 0); for i := 1 to m do begin ReadLn(fi, u); {Ta chỉ cần tính bán bậc ra (deg+) của mỗi đỉnh nên không cần đọc đủ 3 thành phần} Inc(h^[u]); end; for i := 2 to n do h^[i] := h^[i - 1] + h^[i]; Close(fi); {Đến đây, ta xác định được h[u] là vị trí cuối của danh sách kề đỉnh u trong adj^} Reset(fi); {Đọc file lần 2, vào cấu trúc danh sách kề} ReadLn(fi); {Bỏ qua dòng đầu tiên Input file} for i := 1 to m do begin ReadLn(fi, u, v, c); adj^[h^[u]] := v; {Điền v và c vào vị trí đúng trong danh sách kề của u} adjCost^[h^[u]] := c; Dec(h^[u]); end; h^[n + 1] := m; Close(fi); end; procedure Init; {Khởi tạo d[i] = độ dài đường đi ngắn nhất từ S tới i qua 0 cạnh, Heap rỗng} var i: Integer; begin for i := 1 to n do d[i] := maxC; d[S] := 0; FillChar(Free, SizeOf(Free), True); FillChar(Pos, SizeOf(Pos), 0); nHeap := 0; end; procedure Update(v: Integer); {Đỉnh v vừa được sửa nhãn, cần phải chỉnh lại Heap} var parent, child: Integer; begin child := Pos[v]; {child là vị trí của v trong Heap} if child = 0 then {Nếu v chưa có trong Heap thì Heap phải bổ sung thêm 1 phần tử và coi child = nút lá cuối Heap} begin Inc(nHeap); child := nHeap; end; parent := child div 2; {parent là nút cha của child} while (parent > 0) and (d[heap[parent]] > d[v]) do begin {Nếu đỉnh lưu ở nút parent ưu tiên kém hơn v thì đỉnh đó sẽ bị đẩy xuống nút con child} heap[child] := heap[parent]; {Đẩy đỉnh lưu trong nút cha xuống nút con} Pos[heap[child]] := child; {Ghi nhận lại vị trí mới của đỉnh đó} child := parent; {Tiếp tục xét lên phía nút gốc} parent := child div 2; end; {Thao tác "kéo xuống" ở trên tạo ra một "khoảng trống" tại nút child của Heap, đỉnh v sẽ được đặt vào đây} heap[child] := v; Pos[v] := child; end; function Pop: Integer; var r, c, v: Integer; begin Pop := heap[1]; {Nút gốc Heap chứa đỉnh có nhãn tự do nhỏ nhất} v := heap[nHeap]; {v là đỉnh ở nút lá cuồi Heap, sẽ được đảo lên đầu và vun đống} Dec(nHeap); r := 1; {Bắt đầu từ nút gốc} while r * 2 <= nHeap do {Chừng nào r chưa phải là lá} begin {Chọn c là nút chứa đỉnh ưu tiên hơn trong hai nút con} c := r * 2; if (c < nHeap) and (d[heap[c + 1]] < d[heap[c]]) then Inc(c); {Nếu v ưu tiên hơn cả đỉnh chứa trong C, thì thoát ngay} if d[v] <= d[heap[c]] then Break; heap[r] := heap[c]; {Chuyển đỉnh lưu ở nút con c lên nút cha r} Pos[heap[r]] := r; {Ghi nhận lại vị trí mới trong Heap của đỉnh đó} r := c; {Gán nút cha := nút con và lặp lại} end; heap[r] := v; {Đỉnh v sẽ được đặt vào nút r để bảo toàn cấu trúc Heap} Pos[v] := r; end; procedure Dijkstra; var i, u, iv, v, min: Integer; begin Update(1); repeat u := Pop; {Chọn đỉnh tự do có nhãn nhỏ nhất} if u = F then Break; {Nếu đỉnh đó là F thì dừng ngay} Free[u] := False; {Cố định nhãn đỉnh đó} for iv := h^[u] + 1 to h^[u + 1] do {Xét danh sách kề} begin v := adj^[iv]; if Free[v] and (d[v] > d[u] + adjCost^[iv]) then begin d[v] := d[u] + adjCost^[iv]; {Tối ưu hoá nhãn của các đỉnh tự do kề với u} Trace[v] := u; {Lưu vết đường đi} Update(v); {Tổ chức lại Heap} end; end; until nHeap = 0; {Không còn đỉnh nào mang nhãn tự do} end; procedure PrintResult; var fo: Text; begin Assign(fo, OutputFile); Rewrite(fo); if d[F] = maxC then WriteLn(fo, 'Path from ', S, ' to ', F, ' not found') else begin WriteLn(fo, 'Distance from ', S, ' to ', F, ': ', d[F]); while F <> S do begin Write(fo, F, '<-'); F := Trace[F]; end; WriteLn(fo, S); end; Close(fo); end; begin LoadGraph; Init; Dijkstra; PrintResult; end.

8.6. Trường hợp đồ thị không có chu trình - Thứ tự Tô Pô

Ta có định lý sau: Giả sử G = (V, E) là đồ thị không có chu trình (có hướng - tất nhiên). Khi đó các đỉnh của nó có thể đánh số sao cho mỗi cung của nó chỉ nối từ đỉnh có chỉ số nhỏ hơn đến đỉnh có chỉ số lớn hơn.

Phép đánh lại chỉ số theo thứ tự tôpô

Thuật toán đánh số lại các đỉnh của đồ thị có thể mô tả như sau:

Trước hết ta chọn một đỉnh không có cung đi vào và đánh chỉ số 1 cho đỉnh đó. Sau đó xoá bỏ đỉnhnày cùng với tất cả những cung từ u đi ra, ta được một đồ thị mới cũng không có chu trình, và lại đánh chỉ số 2 cho một đỉnh v nào đó không có cung đi vào, rồi lại xoá đỉnh v cùng với các cung từ v đi ra ... Thuật toán sẽ kết thúc nếu như hoặc ta đã đánh chỉ số được hết các đỉnh, hoặc tất cả các đỉnh còn lại đều có cung đi vào. Trong trường hợp tất cả các đỉnh còn lại đều có cung đi vào thì sẽ tồn tại chu trình trong đồ thị và khẳng định thuật toán tìm đường đi ngắn nhất trong mục này không áp dụng được. (Thuật toán đánh số này có thể cải tiến bằng cách dùng một hàng đợi và cho những đỉnh không có cung đi vào đứng chờ lần lượt trong hàng đợi đó, lần lượt rút các đỉnh khỏi hàng đợi và đánh số cho nó, đồng thời huỷ những cung đi ra khỏi đỉnh vừa đánh số, lưu ý sau mỗi lần loại bỏ cung (u, v), nếu thấy bán bậc vào của v = 0 thì đẩy v vào chờ trong hàng đợi, như vậy đỡ mất công duyệt để tìm những đỉnh có bán bậc vào = 0).

Nếu các đỉnh được đánh số sao cho mỗi cung phải nối từ một đỉnh tới một đỉnh khác mang chỉ số lớn hơn thì thuật toán tìm đường đi ngắn nhất có thể mô tả rất đơn giản:

Gọi d[v] là độ dài đường đi ngắn nhất từ S tới v. Khởi tạo d[S] = 0 và d[v] = ∞ với ∀v ≠ S. Ta sẽ tính các d[v] như sau:

for u := 1 to n - 1 do for v := u + 1 to n do d[v] := min(d[v], d[u] + c[u, v]);

(Giả thiết rằng c[u, v] = +∞ nếu như (u, v) không là cung).

Tức là dùng đỉnh u, tối ưu nhãn d[v] của những đỉnh v nối từ u, với u được xét lần lượt từ 1 tới n - 1.

Có thể làm tốt hơn nữa bằng cách chỉ cần cho u chạy từ đỉnh xuất phát S tới đỉnh kết thúc F. Bởi hễ u chạy tới đâu thì nhãn d[u] là không thể cực tiểu hoá thêm nữa.

P_4_08_4.PAS * Đường đi ngắn nhất trên đồ thị không có chu trình program Critical_Path; const InputFile = 'MINPATH.INP'; OutputFile = 'MINPATH.OUT'; max = 100; maxC = 10000; var c: array[1..max, 1..max] of Integer; List, d, Trace: array[1..max] of Integer; {List là danh sách các đỉnh theo cách đánh số mới} n, S, F, count: Integer; procedure LoadGraph; {Nhập dữ liệu, đồ thị không được có chu trình} var i, m, u, v: Integer; fi: Text; begin Assign(fi, InputFile); Reset(fi); ReadLn(fi, n, m, S, F); for u := 1 to n do for v := 1 to n do if u = v then c[u, v] := 0 else c[u, v] := maxC; for i := 1 to m do ReadLn(fi, u, v, c[u, v]); Close(fi); end; procedure Number; {Thuật toán đánh số các đỉnh} var deg: array[1..max] of Integer; u, v: Integer; front: Integer; begin {Trước hết, tính bán bậc vào của các đỉnh (deg-)} FillChar(deg, SizeOf(deg), 0); for u := 1 to n do for v := 1 to n do if (v <> u) and (c[v, u] < maxC) then Inc(deg[u]); {Đưa những đỉnh có bán bậc vào = 0 vào danh sách List} count := 0; for u := 1 to n do if deg[u] = 0 then begin Inc(count); List[count] := u; end; {front: Chỉ số phần tử đang xét, count: Số phần tử trong danh sách} front := 1; while front <= count do {Chừng nào chưa xét hết các phần tử trong danh sách} begin {Xét phần tử thứ front trong danh sách, đẩy con trỏ front sang phần tử kế tiếp} u := List[front]; Inc(front); for v := 1 to n do if c[u, v] <> maxC then {Xét những cung (u, v) và "loại" khỏi đồ thị ⇔ deg-(v) giảm 1} begin Dec(deg[v]); if deg[v] = 0 then {Nếu v trở thành đỉnh không có cung đi vào} begin {Đưa tiếp v vào danh sách List} Inc(count); List[count] := v; end; end; end; end; procedure Init; var i: Integer; begin for i := 1 to n do d[i] := maxC; d[S] := 0; end; procedure FindPath; {Thuật toán quy hoạch động tìm đường đi ngắn nhất trên đồ thị không chu trình} var i, j, u, v: Integer; begin for i := 1 to n - 1 do for j := i + 1 to n do begin u := List[i]; v := List[j]; {Dùng List[i] tối ưu nhãn List[j] với i < j} if d[v] > d[u] + c[u, v] then begin d[v] := d[u] + c[u, v]; Trace[v] := u; end; end; end; procedure PrintResult; {In đường đi từ S tới F} var fo: Text; begin Assign(fo, OutputFile); Rewrite(fo); if d[F] = maxC then WriteLn(fo, 'Path from ', S, ' to ', F, ' not found') else begin WriteLn(fo, 'Distance from ', S, ' to ', F, ': ', d[F]); while F <> S do begin Write(fo, F, '<-'); F := Trace[F]; end; WriteLn(fo, S); end; Close(fo); end; begin LoadGraph; Number; Init; FindPath; PrintResult; end.

8.7. Đường đi ngắn nhất giữa mọi cặp đỉnh - Thuật toán Floyd

Cho đơn đồ thị có hướng, có trọng số G = (V, E) với n đỉnh và m cạnh. Bài toán đặt ra là hãy tính tất cả các d(u, v) là khoảng cách từ u tới v. Rõ ràng là ta có thể áp dụng thuật toán tìm đường đi ngắn nhất xuất phát từ một đỉnh với n khả năng chọn đỉnh xuất phát. Nhưng ta có cách làm gọn hơn nhiều, cách làm này rất giống với thuật toán Warshall mà ta đã biết: Từ ma trận trọng số c, thuật toán Floyd tính lại các c[u, v] thành độ dài đường đi ngắn nhất từ u tới v:

Với mọi đỉnh k của đồ thị được xét theo thứ tự từ 1 tới n, xét mọi cặp đỉnh u, v. Cực tiểu hoá c[u, v] theo công thức:

c[u, v] := min(c[u, v], c[u, k] + c[k, v])

Tức là nếu như đường đi từ u tới v đang có lại dài hơn đường đi từ u tới k cộng với đường đi từ k tới v thì ta huỷ bỏ đường đi từ u tới v hiện thời và coi đường đi từ u tới v sẽ là nối của hai đường đi từ u tới k rồi từ k tới v (Chú ý rằng ta còn có việc lưu lại vết):

for k := 1 to n do for u := 1 to n do for v := 1 to n do c[u, v] := min(c[u, v], c[u, k] + c[k, v]);

Tính đúng của thuật toán:

Gọi ck[u, v] là độ dài đường đi ngắn nhất từ u tới v mà chỉ đi qua các đỉnh trung gian thuộc tập {1, 2, ..., k}. Rõ ràng khi k = 0 thì c0[u, v] = c[u, v] (đường đi ngắn nhất là đường đi trực tiếp).

Giả sử ta đã tính được các ck-1[u, v] thì ck[u, v] sẽ được xây dựng như sau:

Nếu đường đi ngắn nhất từ u tới v mà chỉ qua các đỉnh trung gian thuộc tập {1, 2, ..., k} lại:

• Không đi qua đỉnh k thì tức là chỉ qua các đỉnh trung gian thuộc tập {1, 2, ..., k - 1} thì

ck[u, v] = ck-1[u, v]

• Có đi qua đỉnh k thì đường đi đó sẽ là nối của một đường đi từ u tới k và một đường đi từ k tới v, hai đường đi này chỉ đi qua các đỉnh trung gian thuộc tập {1, 2, ..., k - 1}.

ck[u, v] = ck-1[u, k] + ck-1[k, v].

Vì ta muốn ck[u, v] là cực tiểu nên suy ra: ck[u, v] = min(ck-1[u, v], ck-1[u, k] + ck-1[k, v]).

Và cuối cùng, ta quan tâm tới cn[u, v]: Độ dài đường đi ngắn nhất từ u tới v mà chỉ đi qua các đỉnh trung gian thuộc tập {1, 2, ..., n}.

Khi cài đặt, thì ta sẽ không có các khái niệm ck[u, v] mà sẽ thao tác trực tiếp trên các trọng số c[u,v]. c[u, v] tại bước tối ưu thứ k sẽ được tính toán để tối ưu qua các giá trị c[u, v]; c[u, k] và c[k, v] tại bước thứ k - 1. Tính chính xác của cách cài đặt dưới dạng ba vòng lặp for lồng như trên có thể thấy được do sự tối ưu bắc cầu chỉ làm tăng tốc độ tối ưu các c[u, v] trong mỗi bước.

P_4_08_5.PAS * Thuật toán Floyd program Shortest_Path_by_Floyd; const InputFile = 'MINPATH.INP'; OutputFile = 'MINPATH.OUT'; max = 100; maxC = 10000; var c: array[1..max, 1..max] of Integer; Trace: array[1..max, 1..max] of Integer; {Trace[u, v] = Đỉnh liền sau u trên đường đi từ u tới v} n, S, F: Integer; procedure LoadGraph; {Nhập dữ liệu, đồ thị không được có chu trình âm} var i, m, u, v: Integer; fi: Text; begin Assign(fi, InputFile); Reset(fi); ReadLn(fi, n, m, S, F); for u := 1 to n do for v := 1 to n do if u = v then c[u, v] := 0 else c[u, v] := maxC; for i := 1 to m do ReadLn(fi, u, v, c[u, v]); Close(fi); end; procedure Floyd; var k, u, v: Integer; begin for u := 1 to n do for v := 1 to n do Trace[u, v] := v; {Giả sử đường đi ngắn nhất giữa mọi cặp đỉnh là đường trực tiếp} {Thuật toán Floyd} for k := 1 to n do for u := 1 to n do for v := 1 to n do if c[u, v] > c[u, k] + c[k, v] then {Đường đi từ qua k tốt hơn} begin c[u, v] := c[u, k] + c[k, v]; {Ghi nhận đường đi đó thay cho đường cũ} Trace[u, v] := Trace[u, k]; {Lưu vết đường đi} end; end; procedure PrintResult; {In đường đi từ S tới F} var fo: Text; begin Assign(fo, OutputFile); Rewrite(fo); if c[S, F] = maxC then WriteLn(fo, 'Path from ', S, ' to ', F, ' not found') else begin WriteLn(fo, 'Distance from ', S, ' to ', F, ': ', c[S, F]); repeat Write(fo, S, '->'); S := Trace[S, F]; {Nhắc lại rằng Trace[S, F] là đỉnh liền sau S trên đường đi tới F} until S = F; WriteLn(fo, F); end; Close(fo); end; begin LoadGraph; Floyd; PrintResult; end.

Khác biệt rõ ràng của thuật toán Floyd là khi cần tìm đường đi ngắn nhất giữa một cặp đỉnh khác, chương trình chỉ việc in kết quả chứ không phải thực hiện lại thuật toán Floyd nữa.

8.8. Nhận xét

Bài toán đường đi dài nhất trên đồ thị trong một số trường hợp có thể giải quyết bằng cách đổi dấu trọng số tất cả các cung rồi tìm đường đi ngắn nhất, nhưng hãy cẩn thận, có thể xảy ra trường hợp có chu trình âm.

Trong tất cả các cài đặt trên, vì sử dụng ma trận trọng số chứ không sử dụng danh sách cạnh hay danh sách kề có trọng số, nên ta đều đưa về đồ thị đầy đủ và đem trọng số +∞ gán cho những cạnh không có trong đồ thị ban đầu. Trên máy tính thì không có khái niệm trừu tượng +∞ nên ta sẽ phải chọn một số dương đủ lớn để thay. Như thế nào là đủ lớn? số đó phải đủ lớn hơn tất cả trọng số của các đường đi cơ bản để cho dù đường đi thật có tồi tệ đến đâu vẫn tốt hơn đường đi trực tiếp theo cạnh tưởng tượng ra đó. Vậy nên nếu đồ thị cho số đỉnh cũng như trọng số các cạnh vào cỡ 300 chẳng hạn thì giá trị đó không thể chọn trong phạm vi Integer hay Word. Ma trận c sẽ phải khai báo là ma trận LongInt và giá trị hằng số maxC trong các chương trình trên phải đổi lại là 300 * 299 + 1 - điều đó có thể gây ra nhiều phiền toái, chẳng hạn như vấn đề lãng phí bộ nhớ.

Để khắc phục, người ta có thể cài đặt bằng danh sách kề kèm trọng số hoặc sử dụng những kỹ thuật đánh dấu khéo léo trong từng trường hợp cụ thể. Tuy nhiên có một điều chắc chắn: khi đồ thị cho số đỉnh cũng như trọng số các cạnh vào khoảng 300 thì các trọng số c[u, v] trong thuật toán Floyd và các nhãn d[v] trong ba thuật toán còn lại chắc chắn không thể khai báo là Integer được.

Xét về độ phức tạp tính toán, nếu cài đặt như trên, thuật toán Ford-Bellman có độ phức tạp là O(n3), thuật toán Dijkstra là O(n2), thuật toán tối ưu nhãn theo thứ tự tôpô là O(n2) còn thuật toán Floyd là O(n3). Tuy nhiên nếu sử dụng danh sách kề, thuật toán tối ưu nhãn theo thứ tự tôpô sẽ có độ phức tạp tính toán là O(m). Thuật toán Dijkstra kết hợp với cấu trúc dữ liệu Heap có độ phức tạp O(max(n, m).logn).

Khác với một bài toán đại số hay hình học có nhiều cách giải thì chỉ cần nắm vững một cách cũng có thể coi là đạt yêu cầu, những thuật toán tìm đường đi ngắn nhất bộc lộ rất rõ ưu, nhược điểm trong từng trường hợp cụ thể (Ví dụ như số đỉnh của đồ thị quá lớn làm cho không thể biểu diễn bằng ma trận trọng số thì thuật toán Floyd sẽ gặp khó khăn, hay thuật toán Ford-Bellman làm việc khá chậm). Vì vậy yêu cầu trước tiên là phải hiểu bản chất và thành thạo trong việc cài đặt tất cả các thuật toán trên để có thể sử dụng chúng một cách uyển chuyển trong từng trường hợp cụ thể. Những bài tập sau đây cho ta thấy rõ điều đó.

Bài tập

Bài 1

Giải thích tại sao đối với đồ thị sau, cần tìm đường đi dài nhất từ đỉnh 1 tới đỉnh 4 lại không thể dùng thuật toán Dijkstra được, cứ thử áp dụng thuật toán Dijkstra theo từng bước xem sao:

Bài 2

Trên mặt phẳng cho n đường tròn (n ≤ 2000), đường tròn thứ i được cho bởi bộ ba số thực (Xi, Yi, Ri), (Xi, Yi) là toạ độ tâm và Ri là bán kính. Chi phí di chuyển trên mỗi đường tròn bằng 0. Chi phí di chuyển giữa hai đường tròn bằng khoảng cách giữa chúng. Hãy tìm phương án di chuyển giữa hai đường tròn S, F cho trước với chi phí ít nhất.

Bài 3

Cho một dãy n số nguyên A[1], A[2], ..., A[n] (n ≤ 10000; 1 ≤ A[i] ≤ 10000). Hãy tìm một dãy con gồm nhiều nhất các phần tử của dãy đã cho mà tổng của hai phần tử liên tiếp là số nguyên tố.

Bài 4

Một công trình lớn được chia làm n công đoạn đánh số 1, 2, ..., n. Công đoạn i phải thực hiện mất thời gian t[i]. Quan hệ giữa các công đoạn được cho bởi bảng a[i, j]: a[i, j] = TRUE ⇔ công đoạn j chỉ được bắt đầu khi mà công việc i đã xong. Hai công đoạn độc lập nhau có thể tiến hành song song, hãy bố trí lịch thực hiện các công đoạn sao cho thời gian hoàn thành cả công trình là sớm nhất, cho biết thời gian sớm nhất đó.

Bài 5

Cho một bảng các số tự nhiên kích thước mxn (1 ≤ m, n ≤ 100). Từ một ô có thể di chuyển sang một ô kề cạnh với nó. Hãy tìm một cách đi từ ô (x, y) ra một ô biên sao cho tổng các số ghi trên các ô đi qua là cực tiểu.

Nguồn: Giáo trình Giải thuật và Lập trình - Lê Minh Hoàng - Đại học sư phạm Hà Nội