Bài tập Đồ thị - Tìm đường đi ngắn nhất (bài 3 - trang 124)
Đồ thị G vô hướng, không trọng số được cho bởi danh sách cạnh:

a, b	d, k	e, h
b, c	c, e	e, d
c, d	b, f	d, g
a, f	f, e	g, k
b, e	e, g	h, g
c, k	f, h	h, k

a) Lập danh sách kề của đồ thị, trong đó các đỉnh được sắp xếp theo thứ tự xuất hiện trong danh sách cạnh.
b) Tìm đường đi ngắn nhất của (a,k).

Câu 3. Đề năm 2009:
a. Cho đồ thị G{V, E} vô hướng, liên thông, không trọng số, có n đỉnh 1-n cho bởi ma trận kề A[1..n, 1..n]. Viết thủ tục chi tiết tìm đường đi từ đỉnh u đến đỉnh v sao cho qua ít cạnh nhất.

b. Đồ thị G có hướng, liên thông được cho bởi danh sách cạnh sau:

Nháy vào phần hồng hồng này để ẩn hiện:

Tìm đường đi ngắn nhất từ đỉnh k đến đỉnh e theo thuật toán Dijkastra.

Câu 3b. Đề năm 2007:
b. Đồ thị G có hướng, liên thông được cho bởi danh sách cạnh sau:

Nháy vào phần hồng hồng này để ẩn hiện:

Tìm đường đi ngắn nhất từ đỉnh m đến đỉnh c theo thuật toán Dijkastra.

Giải thuật Dijkstra là một giải thuật để giải bài toán đường đi ngắn nhất nguồn đơn trên một đồ thị có trọng số cạnh mà tất cả các trọng số đều không âm. Nó xác định đường đi ngắn nhất giữa hai đỉnh cho trước, từ đỉnh a đến đỉnh b.
Ở mỗi đỉnh v, giải thuật Dijkstra xác định 3 thông tin: S_v, λ_v và α_v.
S_v: mang giá trị boolean xác định trạng thái được chọn của đỉnh v.
Ban đầu ta khởi tạo tất cả các đỉnh v chưa được chọn, nghĩa là: S_v = false, [You must be registered and logged in to see this image.]V.
λ_v: là chiều dài đường đi mà ta tìm thấy cho đến thời điểm đang xét từ a đến v.
Khởi tạo, λ_v = ∞ ,[You must be registered and logged in to see this image.]v Э V \{a}, λ_a = 0.
p_v: là đỉnh trước của đỉnh v trên đường đi ngắn nhất từ a đến b.
Đường đi ngắn nhất từ a đến b có dạng {a,...,α_v,v,...,b}.
Khởi tạo, p_v = null, [You must be registered and logged in to see this image.]v Э V.

Sau đây là các bước của giải thuật Dijkstra:
B1. Khởi tạo: Đặt S_v: = false [You must be registered and logged in to see this image.]v Э V; λ_v: = ∞ ,v Э V \ {a}, λ_a: = 0.
B2. Chọn v Э V sao cho S_v = false và λ_v = min {λ_t / t Э V, S_t = false}
Nếu λ_v = ∞thì Kết thúc, không tồn tại đường đi từ a đến b.
B3. Đánh dấu đỉnh v, S_v: = true.
B4. Nếu v = b thì Kết thúc và λ_b là độ dài đường đi ngắn nhất từ a đến b.
Ngược lại nếu v ≠ b sang B5.
B5. Với mỗi đỉnh u kề với v mà S_u = false, kiểm tra
Nếu λ_u > λ_v f(v,u) thì λ_u: = λ_v + f(v,u)
Ghi nhớ đỉnh v: α_u: = v.
Quay lại B2.

Trước khi các thành viên giải bài này bằng viết thủ tục, chúng ta sẽ nghiên cứu từng bước làm bằng tay để hiểu thuật toán. Thông thường, trong bài thi việc trình bày bằng tay cũng được số điểm không phải là quá ít (bao giờ cũng có 1 phần, dành cho việc làm bằng tay này). Chúng ta phải làm như thế nào.
Làm mẫu cái đề thi năm 2007 theo cách làm mà sách hướng dẫn (trang 95, 96, sách ôn thi Cao học ngành CNTT, HV KTQS năm 2005).

Đầu tiên là các ký hiệu:
U: Đỉnh hiện tại. Việc xét khoảng cách từ một đỉnh gốc (trong đề này là m) đến một đỉnh đích (trong đề này là c), được chia ra các công đoạn (bước). Mỗi bước, ta có 1 đỉnh hiện tại làm căn cứ, phải chọn trong số các đỉnh kề của nó mà chưa có trong tập V*, đỉnh nào có trọng số ít nhất. Tính khoảng cách từ đỉnh gốc (là m) đến đỉnh này. Đưa đỉnh này vào tập V* để các lần tính sau không xét khoảng cách quay lại đỉnh này nữa.
Giá trị từng ô của bảng này là khoảng cách từ đỉnh gốc m tới đỉnh cần xét.
Nếu đề thi cho ở dạng danh sách kề, thì làm luôn bước này, nhưng nếu đề thi cho ở dạng đồ hình, ta phải lập danh sách kề trước.
Làm bằng tay, đầu tiên ta viết vào bài làm:
Tìm đường đi ngắn nhất P* (m, c)
Sau đó kẻ bảng có n 4 cột (n là số đỉnh của đồ thị). Cột 1 ghi “Bước”, cột 2 ghi “U”, cột 3 bỏ trống cho đẹp, tránh lẫn dữ liệu. Từ cột 4 trở đi ghi lần lượt các đỉnh, nên ghi theo thứ tự đường đi (đừng có ghi lung tung kẻo khó khăn trong việc xét và nhầm lẫn), cột đầu tiên là cột gốc, cột sau cuối của các đỉnh là đích. Cột cuối cùng của bảng ghi “Tập V* ”
Trong bài này ta có 12 đỉnh a, b, c, d, e, f, g, h, i, j, k, m nên phải kẻ tới 16 cột.
Tại bước 0, xác định U chính là m nên ta điền vào bảng tại đỉnh m là 0. Các đỉnh còn lại điền thành ∞. Đưa m vào tập V*.

Bước

U

m

k

j

h

i

e

c

a

b

d

f

g

Tập V*

0

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

Bước 1. Chọn đỉnh U chính là m, nên ta điền tại m khoảng cách là 0. Kiểm tra danh sách đỉnh kề của m xem bằng bao nhiêu thì điền vào. Nếu không phải danh sách kề của m, điền ∞. Do các khoảng cách từ m chỉ có tới k là nhỏ nhất (bằng 2) nên ta sẽ chọn k làm U ở bước kế tiếp. Đưa k bổ sung vào tập V*.

Bước

U

m

k

j

h

i

e

c

a

b

d

f

g

Tập V*

0

0

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

1

m

0

2

∞

6

∞

∞

∞

∞

∞

∞

∞

6

m

Bước 2. Chọn đỉnh U là k, lại kiểm trong danh sách đỉnh kề của k. Lấy trọng số của các đỉnh kề này, cộng với khoảng cách từ m tới k (chính là số 2), được bao nhiêu điền vào. Nếu không phải danh sách kề của k, điền ∞. Nếu đỉnh đã có trong tập V*, bỏ trống (Vì không ai điên mà tính quay lại các đỉnh đã đi qua làm gì). Do các khoảng cách từ m chỉ có tới j là nhỏ nhất (bằng 3) nên ta sẽ chọn j làm U ở bước kế tiếp. Đưa j bổ sung vào tập V*.

Bước

U

m

k

j

h

i

e

c

a

b

d

f

g

Tập V*

0

0

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

1

m

0

2

∞

6

∞

∞

∞

∞

∞

∞

∞

6

m

2

k

2

3

6

7

∞

∞

∞

∞

∞

∞

7

m, k

Bước 3, 4, 5... Tương tự lập luận như bước 2.
Bước 6. Do đỉnh e là đỉnh kề với c nên kết thúc luôn.

Bước

U

m

k

j

h

i

e

c

a

b

d

f

g

Tập V*

0

0

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

1

m

0

2

∞

6

∞

∞

∞

∞

∞

∞

∞

6

m

2

k

2

3

6

7

∞

∞

∞

∞

∞

∞

7

m, k

3

j

3

5

9

∞

∞

∞

∞

∞

∞

∞

m, k, j

4

h

5

6

9

∞

∞

∞

∞

10

7

m, k, j, h

5

i

6

8

∞

∞

∞

12

∞

∞

m, k, j, h, i

6

e

8

10

9

11

9

10

∞

m, k, j, h, i, e

7

c

10

m, k, j, h, i, e, c

Vậy đường đi ngắn nhất từ m đến c theo thuật toán Dijkastra là (m, k, j, h, i, e, c)

@ đ/c Admin: v/v Giải đề thi năm 2007.
- Cách giải còn thiếu bước duyệt ngược lại để kết luận đó là đường đi ngắn nhất.
- Chẳng hạn có ví dụ: Cho danh sách cạnh (a, b, 5); (a, c, 7); (b, c, 3); (c, d, 1). Tìm đường đi ngắn nhất từ a-->d.
- Theo các bước: thứ tự các đỉnh được lấy vào S là: a, b, c, d. Nhưng đường đi ngắn là a, c, d.

Bước lập bảng là để tìm độ dài đường đi ngắn nhất và thứ tự các nút nó sẽ đi qua. Nhưng để đầy đủ thì ta phải thử lại.
Trong sgk viết thiếu đoạn thủ tục này.
@All: các bác thử đọc cái ví dụ trong SGK xem thế nào, chứ bản thân em thấy danh sách kề trước của nó bị sai (nó lấy danh sách kề trước = danh sách kề sau).
Ví dụ: đối với đỉnh a, danh sách kề sau của a là hai đỉnh {b,c}, còn nó làm gì có danh sách kề trước, thế mà sgk lại lấy hai đỉnh b,c
→ dẫn đến nó tìm sai đường đi ngắn nhất và độ dài đường đi ngắn nhất.

Đây là đường đi ngắn nhất theo thuật toán Dijkastra, chứ không phải đường đi ngắn nhất trên thực tế.

Xét đồ thị sau:
[You must be registered and logged in to see this image.]
Nhìn cái đồ thị ta nhận thấy đường đi ngắn nhất từ A đến D sẽ là đường A → B → C → D sẽ có tổng trọng số là 3 + 1 + 3 = 7.
Nhưng theo thuật toán Dijkastra thì nó cứ chọn đoạn có trọng số bé nhất trước. Tức là nó sẽ phải đi A → H → I → J → K → L → D.
Nếu xét đồ thị trên nó lại là đường đi dài nhất, có tổng trọng số bằng 26, nó dài hơn cả A → E → F → G → D (có tổng trọng số = 22).

Cho nên thuật toán là thuật toán, thực tế là thực tế.


Bác Phương nói đúng đấy: A Admin hiểu sai thuật toán. Sonld

@ Admin:

- Thứ nhất: Hiểu sai thuật toán.
- Thứ hai: Thuật toán phải đúng thực tế.

+ Lý do sai thứ nhất: bỏ qua câu lệnh if L(x)> L(a) + f(a, x)... và không xét ngược để tìm ra đường đi ngắn nhất. Trong thuật toán đỉnh x nào có f(x) nhỏ thì được xét trước, chứ không bắt buộc đỉnh tiếp theo phải nằm trên một nhánh của đỉnh trước. Khi kiểm tra tất cả đỉnh kề x, nếu trọng số mới của nó nhỏ hơn trọng số cũ (khi chưa xét x) thì đổi lại trọng số, còn không thì giữ nguyên.

+ Lý do thứ hai: Không biết.


Về thuật toán dựa trên bài toán đ/c vừa nêu ra, tôi tóm lược lời giải thế này:

B1: chọn A
          f(H)= 1, f(E)= 2, f(B)= 3

B2: chọn H, vì f(H)= 1 < f(E)= 2 < f(B)= 3
          f(I) = 2

B3: chọn I (hoặc E cũng được) vì f(E) = f(I) = 2 < f(B)= 3
          f(J)= 10

B4: chọn E (nếu B3 chọn I), vì f(E) = f(I) = 2 < f(B)= 3 < f(J)= 10
          f(F)= 11

B5: chọn B, vì f(B)= 3 < f(J)= 10 < f(B)= 3 < f(F)= 11
          f(C)= 4

B6: chọn C, vì f(C)= 4 < f(J)= 10 < f(F)= 11
          f(D)= 7

B7: chọn D
          f(G)= 9, f(L)= 8

Thoát khỏi vòng lặp, quay ngược lại để tìm đường đi ngắn nhất.

gán x1= D

B1: x2= C, vì C kề D và f(C)+ f(C,D)= 4 + 3 = 7 = f(D)

B2: x3= B, vì B kề C và f(B)+ f(B,C)= 3 + 1 = 4 = f(C)

B3: x4= A, vì A kề B và f(A)+ f(A,B)= 0 + 3 = 3 = f(B)

Vòng lặp dừng.

Output x4, x3, x2, x1.

Nghiên cứu thuật toán Dijkstra trên lớp để có thể viết cho mọi cấu trúc dữ liệu.
Phần không có trọng số.
Hình dung về số mức. Điểm xuất phát mức 0. Các đỉnh kề với mức 0 là mức 1. Các đỉnh kề với các đỉnh mức 1 (mà các đỉnh kề này chưa có dấu mức) sẽ là mức 2. Cứ như thế loang dần ra. Mức nào chứa được đỉnh đích, thì dừng lại. Và đoạn đường đi sẽ có độ dài chính là mức. Đỉnh u là đỉnh xuất phát, đỉnh v là đỉnh đích. Việc chúng ta là tìm khoảng cách u đến v.

A. Khởi tạo:
for all x Э V λ(x): = + ∞;// Đưa tất cả khoảng cách các đỉnh với đỉnh xuất phát là vô cùng.
m: = 0; //Đặt mức để cho dễ trình bày
λ (u): = m;// Đặt nhãn của điểm u chính là m.
A(m): = {u}//Khởi tạo tập A chứa một phần tử u.

B. Chọn đỉnh
While λ (v) = + ∞
          1) A(m+1) := Ø;
          2) for each a Э A(m)
                    for each x Э V⁺ (a) //x thuộc tập đỉnh kề
                              if λ (x) = + ∞
                                        λ (x) := m + 1;
                                        A(m+1): = A(m+1) U {x} //Thêm vào A(m+1) đỉnh {x}
          3) m:= m+1;

C. Xác định đường đi
Um: = v
for j := m - 1 downto 1
          Uj Э V^-(Uj+1) ∩ Aj;
U₀ : =U;

D. Output (U₀, ..., Um), λ (v)

Phần có trọng số.
Hình dung về số mức. Sử dụng một tập S để lưu các đỉnh có dấu hiệu tốt.
A. Khởi tạo:
for all x Э V λ(x): = + ∞;// Đưa tất cả khoảng cách các đỉnh với đỉnh xuất phát là vô cùng.
λ (u): = 0;// Đặt nhãn của điểm u chính là m.
S:= Ø //Khởi tạo tập S ban đầu rỗng, cho dễ viết ở phần sau.

B. Chọn đỉnh
While v ! Э S
          1) Tìm a sao cho λ (a)= min { λ (x) : x Э V\S} // x ngoài S
                    S := S U {a} //đưa {a} vào tập S
          2) for each x Э V⁺ (a) //xét tất cả các đỉnh kề sau của đỉnh này
                    if λ (a) + f(a, x) < λ (x)
                              λ (x) := λ (a) + f(a, x);

C. Xác định đường đi
Uo: = v; j := 0;
while Uj ≠ u
          Tìm x Э V^-(Uj); sao cho // Kề với trước Uj
          λ (x) + f(x, Uj) = λ (Uj)
          Uj+1 : = x; j := J+1;

D. Output (U_j, Uj-1..., Uo), λ (v)

Một số cách viết hàm để sử dụng:
Giả sử đồ thị có hướng, cho bởi danh sách kề từ 1 đến n. Có m cạnh cho bởi danh sách cạnh
D: array (1..m) of Cạnh;
Cạnh = Record
          d, c: Tên đỉnh;
          t: giá trị trọng số;
          End.

1. Hàm Kề (u, v: Tên đỉnh), cho giá trị TRUE nếu 2 đỉnh kề nhau hay (u, v) Э E
Func. Kề (u, v: tên đỉnh) Boolean;
i: = 1
WHILE (i ≤ m) AND (D (i).đ ≠ u OR D(i).c ≠ v) DO i++;
Kề := (i ≤ m)

2. Hàm f(u, v: Tên đỉnh): Giá trị là trọng số của 2 đỉnh, hoặc ∞ nếu 2 đỉnh không kề nhau.
Func. f (u, v: tên đỉnh): Giá trị;
i: = 1
WHILE (i ≤ m) AND (D (i).đ ≠ u OR D(i).c ≠ v) DO i++;
IF i ≤ m THEN f := D(i).t
          ELSE f:= ∞;

3. Viết một thủ tục tìm đường đi ngắn nhất tới 2 đỉnh u, v cho trước
Proc. ShortPath (u, v: tên đỉnh);
1. FOR x := 1 TO n DO λ(x) := ∞; λ(u) := 0; s(x): = 0;
stop := false;
2. WHILE s(v) := 0 & !Stop DO
          a) a:= v;
          FOR x := 1 TO n DO
                    IF (s(a) := 0) & (λ(a) > λ(x)) THEN a := x;
          s(a) := 1;
          IF λ(a) := ∞ THEN stop := TRUE;
          b) FOR x := 1 TO n DO
                    IF Kề(a, x) & (λ(x) > λ (a)+ f(a, x)) THEN λ(x) := λ(a) + f(a, x)
3. IF stop := false THEN
k := 1; α (k) := v;
WHILE α(k) ≠ u DO
          x := 1;
          WHILE !Kề( x, α(k)) OR (λ(x) ≠ (λ(α(k) + f(α(k), x)) DO x++;
          k++; α(k) := x;
4. IF !Stop THEN Output (λ(v) , α(k), α(k-1),..., α(1);
          ELSE Output("Hai đỉnh không thuộc vùng liên thông, không có đường đi từ u đến v")

Một dạng dữ liệu khác là danh sách liên kết.
Cho đồ thị G liên thông có n đỉnh đánh số từ 1 đến n cho bởi danh sách kề.
V: array (1..n) of DanhSach
DanhSach = ^Đỉnh;
Đỉnh = record
          t: tên đỉnh
          Next: DanhSach;
          End

Viết thủ tục tìm đường đi ngắn nhất nối u, v

---

PROC DuongDiNganNhat (u, v: Tên đỉnh)
1. FOR i := 1 to n DO λ(i) := ∞;
λ(u) := 0; kc := 0;
2. WHILE λ(v) ≠ ∞ DO
          a) FOR j := 1 TO n DO
                    IF λ(j) = kc THEN
                              p := V(j);
                              WHILE p ≠ Nil DO
                                        IF λ(p^.t) = ∞ THEN λ(p^.t) := kc + 1;
          b) kc := kc +1;
3. α(kc) : = v
FOR i := kc - 1 DOWNTO 1 DO
          P := V(α(i + 1))
          WHILE λ(p^.t) ≠ i THEN p := p^.Next
          α(i) := p^.t
α(0) := u;
4. Output (kc, α(0), α(1)... α(kc))

Anh/chị giải thích kỹ đoạn này cho e hiểu rõ hơn,cố gắng để hiểu mà mãi k hiểu.
3. IF stop := false THEN
k := 1; α (k) := v;
WHILE α(k) ≠ u DO
x := 1;
WHILE !Kề( x, α(k)) OR (λ(x) ≠ (λ(α(k) + f(α(k), x)) DO x++;
k++; α(k) := x;

Admin: Đoạn này là đoạn kiểm tra xem đúng đỉnh kề có nhãn cần chọn không, đúng rồi thì đưa vào danh sách đỉnh thôi.

cho mình hỏi toán tử stop ở đây là gì vậy?

Code:


Proc. ShortPath (u, v: tên đỉnh);
1. FOR x := 1 TO n DO λ(x) := ∞; λ(u) := 0; s(x): = 0;
stop := false;
2. WHILE s(v) := 0 & !Stop DO
          a) a:= v;
          FOR x := 1 TO n DO
                    IF (s(a) := 0) & (λ(a) > λ(x)) THEN a := x;
          s(a) := 1;
          IF λ(a) := ∞ THEN stop := TRUE;
          b) FOR x := 1 TO n DO
                    IF Kề(a, x) & (λ(x) > λ (a)+ f(a, x)) THEN λ(x) := λ(a) + f(a, x)
3. IF stop := false THEN
k := 1; α (k) := v;
WHILE α(k) ≠ u DO
          x := 1;
          WHILE !Kề( x, α(k)) OR (λ(x) ≠ (λ(α(k) + f(α(k), x)) DO x++;
          k++; α(k) := x;
4. IF !Stop THEN Output (λ(v) , α(k), α(k-1),..., α(1);
          ELSE Output("Hai đỉnh không thuộc vùng liên thông, không có đường đi từ u đến v")


bài này khó hiểu quá, có bài nào bằng C thì cho mình với!

Admin đã viết:
Bước 1. Chọn đỉnh U chính là m, nên ta điền tại m khoảng cách là 0. Kiểm tra danh sách đỉnh kề của m xem bằng bao nhiêu thì điền vào. Nếu không phải danh sách kề của m, điền ∞. Do các khoảng cách từ m chỉ có tới k là nhỏ nhất (bằng 2) nên ta sẽ chọn k làm U ở bước kế tiếp. Đưa k bổ sung vào tập V*.

Bước

U

m

k

j

h

i

e

c

a

b

d

f

g

Tập V*

0

0

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

∞

1

m

0

2

∞

6

∞

∞

∞

∞

∞

∞

∞

6

m

Admin cho em hỏi chút. Theo đầu bài là cho Đồ thị G có hướng,nhưng trong các bước xét em thấy anh admin xét đồ thị vô hướng thì phải.
Như trong bước 1 này anh xét m kề với đỉnh k, h, g. Nhưng đầu bài đưa ra thì m → k, m → h, còn m !→ g.
Mọi người xem lại giúp em với. Thanks.