Bài giảng Lý thuyết đồ thị - Chương 5: Bài toán đường đi ngắn nhất

Chương 5Bài toán đường đi ngắn nhấtBài toán: Cho đồ thị G = (V, E) và hai đỉnh a, b. Tìm đường đi ngắn nhất (nếu có) đi từ đỉnh a đến đỉnh b trong đồ thị G. Ý nghĩa thực tế: 	Bài toán giúp chúng ta chọn các hành trình tiết kiệm nhất (quãng đường, thời gian, chi phí ...) trong giao thông, lập lịch thi công công trình một cách tối ưu, xử lý trong truyền tin ...Bài toán đường đi ngắn nhất1) Lần lượt gán nhãn cho các đỉnh của đồ thị, mỗi đỉnh không quá một lần, như sau:	- Đỉnh a được gán nhãn là số 0.	- Những đỉnh kề với đỉnh a được gán số 1.	- Những đỉnh kề với đỉnh đã được gán nhãn số 1, được gán số 2.	- Tương tự, những đỉnh kề với đỉnh đã được gán số i được gán nhãn là số i+1.2) Thực hiện cho đến khi gán được nhãn cho đỉnh b hoặc không gán nhãn được nữa.Nếu đỉnh b được gán nhãn nào đó là k thì kết luận có đường đi ngắn nhất từ đỉnh a tới đỉnh b với độ dài k, ngược lại thì trả lời là không có.Bài toán đường đi ngắn nhất (tt)Định nghĩa 8.1: Đồ thị G được gọi là đồ thị có trọng số nếu trên mỗi cạnh (i, j) của đồ thị được gán một số nguyên không âm c(i,j). 	Nhãn c(i,j) trên cạnh (i, j) của đồ thị thường biểu diễn “chi phí” thực tế để đi qua cạnh này. 	Ký hiệu đồ thị có trọng số là (G, c). Bài toán đường đi ngắn nhất (tt)Độ dài của đường đi trong đồ thị có trọng số bằng tổng các trọng số của các cạnh trên đường đi đó.Độ dài đường đi có trọng số bé nhất đi từ đỉnh a đến đỉnh b được gọi là khoảng cách từ đỉnh a đến đỉnh b. Nếu không có đường đi từ a đến b thì đặt khoảng cách bằng .Bài toán 	Cho đồ thị có trọng số (G, c) và hai đỉnh a, b thuộc G. Hãy tìm đường đi có tổng trọng số bé nhất (nếu có) đi từ đỉnh a đến đỉnh b.Bài toán đường đi ngắn nhất (tt)Thuật toán 8.2 	1. Với đỉnh xuất phát a, gán nhãn d(a) := 0.	2. Nếu có cạnh (i, j) mà đỉnh i đã được gán nhãn và đỉnh j chưa được gán nhãn hoặc đỉnh j đã được gán nhãn nhưng d(i) + c(i,j) < d(j) thì giảm nhãn: 	d(j) := d(i) + c(i,j).	3. Lặp lại bước 2 cho đến khi không gán hoặc giảm nhãn được nữa.Thuật toán DijkstraĐịnh lý 8.1: Tại mỗi đỉnh b giá trị nhãn d(b) cuối cùng(nếu có) chính là độ dài của đường đi ngắn nhất từ đỉnh a đến đỉnh b.Chứng minh:	Sau khi đã thực hiện xong thuật toán trên, nếu nhãn d(b) xác định thì ta có đường đi từ đỉnh a tới đỉnh b.Thuật toán Dijkstra (tt)Khôi phục đường đi từ a đến b như sau:Xuất phát từ đỉnh b, tìm cạnh có đỉnh cuối là b và đỉnh đầu là i sao cho:	d(i) + c(i,b) = d(b).Đỉnh i như thế chắc chắn phải tồn tại vì xảy ra đẳng thức ở lần gán hoặc giảm nhãn d(j) cuối cùng. Cứ tiếp tục như thế cho đến khi gặp đỉnh a.Thuật toán Dijkstra (tt)Giả sử ta nhận được dãy các cạnh:	 (a, a1) , (a1, a2) , ... , (ak-1, b) mà trên đó: 	d(a) + c(a,a1) = d(a1)	d(a1) + c(a1,a2) = d(a2)	.. . ..	. . . .. .. . . . . . . .. . . 	d(ak-1) + c(ak-1,b) = d(b).Thuật toán Dijkstra (tt)Cộng từng vế và khử các giá trị chung ở cả hai vế ta có: c(a,a1) + c(a1,a2) + ... + c(ak-1 ,b) = d(b).Vậy giá trị nhãn d(b) chính là độ dài đường đi nói trên. Bất kỳ đường đi nào khác từ đỉnh a đến đỉnh b cũng có các hệ thức tương tự nhưng có dấu . Vậy nhãn d(b) là độ dài của đường đi ngắn nhất.Thuật toán Dijkstra (tt)Ví dụ (giải thuật Dijkstra)Tìm đường đi ngắn nhất từ đỉnh 1 đến mọi đỉnh còn lạiBảng nhãn theo GT Dijkstra1234567800,11,14,13,1Vc,1Vc,1Vc,1Vc,112,2--6,2------23,1--3,3----3--3,35,4--45,6--10,655,46,566,5Giải thuật Bellman - Fordij1j2jjkđường điđường điđường đi...cungcungcungXNguyên lý Bellman:d[j] = Min {d[v] + c(v,j), v thuộc X}Giải thuật Bellman – Ford (tt)	void BellmanFord(int x){	//khoi tao://lap:}