Mở đầu Trong phần này chúng ta chỉ xét đồ thị có hƣớng G=(V,E) và |V|=n,|E|=m với các cung đƣợc gán trọng số, nghĩa là, mỗi cung (u,v) E của nó đƣợc đặt tƣơng ứng với một số thực a(u,v) gọi là trọng số của nó. Chúng ta sẽ đặt a(u,v)= , nếu (u,v) E. , vp là một đƣờng đi trên G, thì độ dài của nó đƣợc định nghĩa là tổng sau: tức là, độ dài của đƣờng đi chính là tổng các trọng số trên các cung của nó. (Chú ý rằng nếu chúng ta gán trọng số cho tất cả các cung đều bằng 1, thì ta thu đƣợc định nghĩa độ dài đuờng đi nhƣ là số cung của đƣờng đi.
Bài toán tìm đƣờng đi ngắn nhất trên đồ thị dƣới dạng tổng quát có thể đƣợc phát biểu dƣới dạng tổng quát nhƣ sau: Tìm đƣờng đi có độ dài nhỏ nhất từ một đỉnh xuất phát s V đến đỉnh cuối (đích) t V. Đƣờng đi nhƣ vậy sẽ gọi là đường đi ngắn nhất từ s đến t còn độ dài của nó sẽ kí hiệu là d(s,t) và còn gọi là khoảng cách từ s đến t (khoảng cách định nghĩa nhƣ vậy có thể là số âm). Nếu nhƣ không tồn tại đƣờng đi từ s đến t thì ta đặt d(s,t)= từ đó ta thấy chu trình trong đồ thị có độ dài dƣơng, thì trong đƣờng đi ngắn nhất không có đỉnh nào lặp lại (đƣờng đi nhƣ thế gọi là đường đi cơ bản). Trang 8 Mặt khác, nếu trong đồ thị có chu trình với độ dài âm (gọi là chu trình âm) thì khoảng cách giữa 1 số cặp đỉnh nào đó của đồ thị có thể là 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 các đỉnh này có độ dài nhỏ hơn bất kì số thực cho trƣớc nào.
Trong truờng hợp nhƣ vậy, có thể đặt vấn đề tìm đƣờng đi cơ bản ngắn nhất, tuy nhiên bài toán đặt ra sẽ trở nên phức tạp hơn rất nhiều, bởi vì nó chứa bài toán xét sự tồn tại đƣờng đi Hamilton trong đồ thị nhƣ là một trƣờng hợp riêng. Trƣớc hết cần chú ý rằng nếu biết khoảng cách từ s đến t, thì đƣờng đi ngắn nhất từ s đến t, trong trƣờng hợp trọng số không âm, có thể tìm một cách dễ dàng. Để tìm đƣờng đi, chỉ cần chú ý là đối với cặp đỉnh s,t V tuỳ ý (s t) luôn tìm đƣợc đỉnh v sao cho: d(s,t) = d(s,v) + a(v,t) Thật vậy đỉnh v nhƣ vậy chính là đỉnh đi trƣớc đỉnh t trong đƣờng đi ngắn nhất từ s đến t. Tiếp theo ta có thể tìm đƣợc u sao cho d(s,v)=d(s,u)+a(u,v),.
Từ giả thiết về tính không âm của các trọng số dễ dàng suy ra rằng dãy t,v,u. không chứa đỉnh lặp lại và kết thúc ở đỉnh s. Rõ ràng dãy thu đƣợc xác định đƣờng đi ngắn nhất từ s đến t.2 Đƣờng đi ngắn nhất xuất phát từ một đỉnh Phần lớn các thuật toán tìm khoảng cách giữa hai đỉnh s và t đƣợc xây dựng nhờ kỹ thuật tính toán mà ta có thể mô tả nhƣ sau: từ ma trận trọng số a[u,v],u,v V, ta tính cận trên d[v] của khoảng cách từ s đến tất cả các đỉnh v V. Mỗi khi phát hiện d[u]+a[u,v]<d[v] cận trên d[v] sẽ đƣợc tốt lên: d[v]=d[u]+a[u,v].
Quá trình đó sẽ kết thúc khi nào chúng ta không làm tốt thêm đƣợc bất cứ cận trên nào. Khi đó, rõ ràng giá trị của mỗi d[v] sẽ cho ta khoảng cách từ mỗi đỉnh s đến v. Khi thể hiện kỹ thuật tính toán này trên máy tính, cận trên d[v] sẽ đƣợc gọi là nhãn của đỉnh v, còn việc tính lại các cận trên này sẽ gọi là phép gán nhãn cho đồ thị và toàn bộ thủ tục thƣờng gọi là thủ tục gán nhãn. Nhận thấy rằng để tính khoảng cách từ s đến tất cả các đỉnh còn lại của đồ thị.
Hiện nay vẫn chƣa biết thuật toán nào cho phép tìm đƣờng đi ngắn nhất giữa hai đỉnh làm việc thực sự hiệu quả hơn những thuật toán tìm đƣờng đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại. Sơ đồ tính toán mà ta vừa mô tả còn chƣa là xác định, bởi vì còn phải chỉ ra thứ tự chọn các đỉnh u và v để kiểm tra điều kiện. Thứ tự chọn này có ảnh hƣởng rất lớn đến hiệu quả thuật toán.3 Đƣờng đi trong đồ thị không có chu trình. Bây giờ ta xét trƣờng hợp riêng thứ hai của bài toán tìm đƣờng đi ngắn nhất, mà để giải nó có thể xây dựng thuật toán với độ phức tạp tính toán O(n2), đó là đồ thị không có chu trình (còn trọng số trên các cung có thể là các số thực tuỳ ý).
Trƣớc hết ta chứng minh định lý sau. Giả sử G là đồ thị không có chu trình. Khi đó các đỉnh của nó có thể đánh số sao cho mỗi cung của đồ thị chỉ hướng từ đỉnh có chỉ số nhỏ hơn đến đỉnh có chỉ số lớn hơn, nghĩa là mỗi cung của nó có thể biểu diễn dưới dạng (v[i],v[j]), trong đó i<j. Đồ thị trong hình sau có các đỉnh đƣợc đánh số thỏa mãn điều kiện nêu trong định lý.
Đồ thị không có chu trình Để chứng minh định lý ta mô tả thuật toán sau, cho phép tìm ra cách đánh số thỏa mãn điều kiện định lý. Void Numbering; Đầu vào: Đồ thị có hướng G=(V,E) với n đỉnh không chứa chu trình được cho bởi danh sách kề Ke(v),v V Đầu ra: Với mỗi đỉnh v V chỉ số NR[u] < NR[v]. { For v V do Vao[v]:=0; (* tinh Vao[v]=deg-(v) *) For u V do For v Ke(u) do Vao[v]:=Vao[v] + 1; QUEUE:= ; For v V do If Vao[v]=0 then QUEUE v ; Num :=0; Trang 10 While QUEUE do { u QUEUE; Num :=num +1; NR[u] :=num; For v Ke(u) do { Vao[v]:=Vao[v] - 1; If Vao[v]=0 then QUEUE v ; } } } Thuật toán đƣợc xây dựng dựa trên ý tƣởng rất đơn giản sau: Rõ ràng trong đồ thị không có chu trình bao giờ cũng tìm đƣợc đỉnh có bán bậc vào bằng 0 (không có cung đi vào). Thực vậy, bắt đầu từ đỉnh v1 nếu có cung đi vào nó từ v2 thì ta lại chuyển sang xét đỉnh v2.
Nếu có cung v3 đi vào v2, thì ta chuyển sang xét v3. Do đồ thị là không có chu trình nên sau một số hữu hạn lần chuyển nhƣ vậy ta phải đi đến đỉnh không có cung đi vào. Thoạt tiên, tìm các đỉnh nhƣ vậy của đồ thị. Rõ ràng ta có thể đánh số chúng theo một thứ tự tuỳ ý bắt đầu từ 1.
Tiếp theo, loại bỏ khỏi đồ thị những đỉnh đã đƣợc đánh số cùng các cung đi ra khỏi chúng, ta thu đƣợc đồ thị mới cũng không có chu trình, và thủ tục đƣợc lặp lại với đồ thị mới này. Quá trình đó sẽ đƣợc tiếp tục cho đến khi tất cả các đỉnh của đồ thị đƣợc đánh số. Trang 11 CHƢƠNG 2 MỘT SỐ THUẬT TOÁN TÌM ĐƢỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ 2. MỘT SỐ KHÁI NIỆM Xét đồ thị có hƣớng G=(V,E), |V|=n, |E|=m với các cung đƣợc gán trọng số, nghĩa là, mỗi cung (u, v) E của nó đƣợc đặt tƣơng ứng với một số thực a(u, v) gọi là trọng số của nó.
Chúng ta sẽ đặt a(u, v) = , nếu (u,v) E., vp là một đƣờng đi trên G, thì độ dài của nó đƣợc định nghĩa là tổng sau ∑ tức là, độ dài của đƣờng đi chính là tổng của các trọng số trên các cung của nó. Bài toán tìm đƣờng đi ngắn nhất trên đồ thị dƣới dạng tổng quát có thể phát biểu nhƣ sau: tìm đƣờng đi có độ dài nhỏ nhất từ một đỉnh xuất phát s V đến đỉnh cuối (đích) t V. Đƣờng đi nhƣ vậy ta sẽ gọi là đƣờng đi ngắn nhất từ s đến t còn độ dài của nó ta sẽ ký hiệu là d(s, t) và còn gọi là khoảng cách từ s đến t (khoảng cách định nghĩa nhƣ vậy có thể là số âm). Nếu nhƣ không tồn tại đƣờng đi từ s đến t thì ta sẽ đặt d(s, t)=.
Rõ ràng, nếu nhƣ mỗi chu trình trong đồ thị đều có độ dài dƣơng, trong đƣờng đi ngắn nhất không có đỉnh nào bị lặp lại (đƣờng đi không có đỉnh lặp lại sẽ gọi là đƣờng đi cơ bản). Mặt khác nếu trong đồ thị có chu trình với độ dài âm (chu trình nhƣ vậy để gọi ngắn gọn ta gọi là chu trình âm) thì khoảng cách giữa một số cặp đỉnh nào đó của đồ thị có thể là 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 các đỉnh này có độ dài nhỏ hơn bất cứ số thực cho trƣớc nào. Trong những trƣờng hợp nhƣ vậy, có thể đặt vấn đề tìm đƣờng đi cơ bản ngắn nhất, tuy nhiên bài toán đặt ra sẽ trở nên phức tạp hơn rất nhiều, bởi vì nó chứa bài toán xét sự tồn tại đƣờng đi Hamilton trong đồ thị nhƣ là một trƣờng hợp riêng. Trƣớc hết cần chú ý rằng nếu biết khoảng cách từ s đến t, thì đƣờng đi ngắn nhất từ s đến t, trong trƣờng hợp trọng số không âm, có thể tìm đƣợc một cách dễ dàng.
Để Trang 12 tìm đƣờng đi, chỉ cần để ý là đối với cặp đỉnh s, t V tuỳ ý (s <> t) luôn tìm đƣợc đỉnh v sao cho d(s, t) = d(s, v) + a(v, t). Thực vậy, đỉnh v nhƣ vậy chính là đỉnh đi trƣớc đỉnh t trong đƣờng đi ngắn nhất từ s đến t. Tiếp theo ta lại có thể tìm đƣợc đỉnh u sao cho d(s, v) = d(s, u) + a(u,v),. Từ giả thiết về tính không âm của các trọng số dễ dàng suy ra rằng dãy t, v, u,.
không chứa đỉnh lặp lại và kết thúc ở đỉnh s. Rõ ràng dãy thu đƣợc xác định (nếu lật ngƣợc thứ tự các đỉnh trong nó) đƣờng đi ngắn nhất từ s đến t. Từ đó ta có thuật toán sau đây để tìm đƣờng đi ngắn nhất từ s đến t khi biết độ dài của nó. Chú ý rằng độ phức tạp tính toán của thuật toán là O(n 2), do để tìm đỉnh u ta phải xét qua tất cả các đỉnh của đồ thị.
Tất nhiên, ta cũng có thể sử dụng kỹ thuật ghi nhận đƣờng đi đã trình bày trong chƣơng 3: dùng biến mảng Truoc[v], v V, để ghi nhớ đỉnh đi trƣớc v trong đƣờng đi tìm kiếm.