Bài giảng Lý thuyết đồ thị: Chương 5

CHƯƠNG 5

ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ

Tôn Quang Toại Khoa CNTT, Đại học Ngoại ngữ ‐ Tin học TP.HCM

Nội dung

Các khái niệm mở đầu Phát biểu bài toán Thuật toán Dijkstra Thuật toán Ford – Bellman Thuật toán Floyd

Các khái niệm mở đầu

Đồ thị có trọng số: Đồ thị G=(V, E) có trọng số khi mỗi cạnh e=(u,v) của đồ thị được gán với một con số w(u,v) và được gọi là trọng số của cạnh e.

(cid:2870)

(cid:2869)

Đường đi: Đường đi giữa 2 đỉnh s và t được cho bởi là dãy đỉnh (cid:3040) trong đó:

(cid:2869)

(cid:3040)

(cid:3036)

(cid:3036)(cid:2878)(cid:2869)

Các khái niệm mở đầu

Độ dài đường đi: Độ dài đường đi là tổng trọng số của tất cả các cạnh trên đường đi đó

(cid:3040)(cid:2879)(cid:2869)

(cid:3036)(cid:2880)(cid:2869)

𝑤 𝑝 (cid:3404) (cid:3533) 𝑤(cid:4666)𝑥(cid:3036), 𝑥(cid:3036)(cid:2878)(cid:2869)(cid:4667)

Phát biểu bài toán

Ví dụ:

18 b

c

12

p = (a, d, f, g) w(p) = 6 + 8 + 2 = 16

4

3

2

7 g

6 a

d

8

2

3

9

4 f

e

14

Các khái niệm mở đầu

Biểu diễn đồ thị trọng số Cách 1: Ma trận trọng số

𝑣(cid:3036)(cid:3037) (cid:3404) (cid:4682) 0/∞ 𝑛ế𝑢 (cid:4666)𝑖, 𝑗(cid:4667) ∉ 𝐸 𝑤(cid:4666)𝑖, 𝑗(cid:4667) 𝑛ế𝑢(cid:4666)𝑖, 𝑗(cid:4667) ∈ 𝐸

int[,] v; int n;

Các khái niệm mở đầu

Cách 2: Danh sách cạnh LinkedList> e;

Cách 3: Danh sách kề LinkedList>[] v;

Phát biểu bài toán

Phát biểu bài toán:

Cho đồ thị G=(V, E) có trọng số và hai đỉnh s và t cho trước. Hãy tìm 1 đường đi từ s đến t sao cho độ dài đường đi là ngắn nhất

Phát biểu bài toán

18 c

b

12

Ví dụ:

4

3

2

7

p = (a, d, f, g) w(p) = 6 + 8 + 2 = 16

g = t

6 s = a

d

8

2

3

9

4 f

e

pshortest = (s, ,t) w(pshortest) =

14

Thuật toán Dijkstra

Giả định của thuật toán Dijkstra Không có cạnh âm trong đồ thị s và t liên thông với nhau

Ý tưởng thuật toán Dijkstra:

Mỗi đỉnh của đồ thị, ta gán một giá trị dist[i]: là độ dài đường đi ngắn nhất từ s đến i. Nhiệm vụ: Giảm giá trị mảng dist[ ] từng bước.

Thuật toán Dijkstra

Thuật toán Dijkstra:

Input: G=(V, E) và 2 đỉnh s, t Output: 𝑑𝑖𝑠𝑡(cid:4670)(cid:4671)

Bước 1 (Khởi tạo)

• 𝑑𝑖𝑠𝑡 𝑖 (cid:3404) (cid:3397)∞, ∀𝑖 ∈ 𝑉 • 𝑑𝑖𝑠𝑡 𝑠 (cid:3404) 0 • Tập S=V (S là tập đỉnh chưa xét)

Bước 2 (Lặp)

• Tìm min: Chọn đỉnh 𝑎 ∈ 𝑆 sao cho 𝑑𝑖𝑠𝑡 𝑎 có giá trị nhỏ nhất

• Cập Nhật: Với mọi đỉnh b kề đỉnh a

– Nếu dist[b]>dist[a] + w(a,b) thì dist[b]=dist[a] + w(a,b) và pre[b]=a

• S = S ‐ {a} (đỉnh a đã xét xong, bỏ khỏi tập S)

Lặp cho đến khi t  S (đỉnh t được xét)

Thuật toán Dijkstra

Giải thích bước cập nhật:

Khi gán 𝑑𝑖𝑠𝑡 𝑏 (cid:3404) 𝑑𝑖𝑠𝑡 𝑎 (cid:3397) 𝑤 𝑎, 𝑏 tức là ta đã phát hiện ra 1 đường đi mới đến b có độ dài ngắn hơn

𝑑𝑖𝑠𝑡(cid:4666)𝑏(cid:4667) 𝑏

𝑑𝑖𝑠𝑡 𝑏 (cid:3408) 𝑑𝑖𝑠𝑡 𝑎 (cid:3397) 𝑤(cid:4666)𝑎, 𝑏(cid:4667)

Đường đi cũ

Đường đi mới

𝑤(cid:4666)𝑎, 𝑏(cid:4667)

𝑠

𝒂 𝑑𝑖𝑠𝑡(cid:4666)𝑎(cid:4667)

Và đường đi đó trước khi tới b phải qua a vì vậy để tìm liệt kê các đỉnh đường đi chúng ta dùng 1 mảng pre[]. Trong đó pre[b]=a cho biết đỉnh ngay trước đỉnh b là đỉnh a.

Ví dụ

Ví dụ 1: Dùng thuật toán Dijkstra Tìm đường đi ngắn nhất từ a đến g

18 c

b

12

4

3

2

7 g=t

6 d

s=a

8

2

3

9

4 f

e

14

Ví dụ

Lưu ý:

Thuật toán Dijkstra có thể áp dùng tìm đường đi ngắn nhất từ một đỉnh đến tất các các đỉnh còn lại (chúng ta chỉ cần sửa lại điều kiện kết thúc vòng lặp là S=Ø)