Trong một trò chơi, người chơi muốn tìm đường đi ngắn nhất để đi từ A đến P

Đáp án: 21

Cách 1: Liệt kê

Bảng liệt kê các lộ trình từ A đến P

Lộ trình di chuyển	Chi tiết các đoạn đường	Tổng quãng đường
\(A \to B \to N \to P\)	\(8 + 9 + 10\)	27
\(A \to B \to M \to P\)	\(8 + 8 + 6\)	22
\(A \to B \to M \to N \to P\)	\(8 + 8 + 6 + 10\)	32
\(A \to C \to B \to N \to P\)	\(7 + 7 + 9 + 10\)	33
\(A \to C \to M \to P\)	\(7 + 8 + 6\)	21
\(A \to C \to M \to N \to P\)	\(7 + 8 + 6 + 10\)	31

Dựa vào bảng trên, học sinh có thể thấy ngay lộ trình qua các điểm \(A \to C \to M \to P\) là con đường ngắn nhất với tổng giá trị là 21.

Cách 2: Thuật toán Dijkstra

Quy ước: Điểm B có nhãn có dạng [d, A], trong đó d là khoảng cách ngắn nhất từ A đến điểm B.

Diễn giải thuật toán

Bước 1: Chọn đỉnh A làm vĩnh viễn

Từ A, ta cập nhật nhãn tạm thời cho các đỉnh kề nó là B và C.

B có nhãn [8, A] và C có nhãn [7, A].

Vì \(7 < 8\), ta chọn đỉnh C để cố định nhãn vĩnh viễn.

Bước 2: Từ đỉnh vĩnh viễn C

Xét các đỉnh kề C chưa có nhãn vĩnh viễn là B và M.

Đến B qua C: \(7 + 7 = 14\) (lớn hơn nhãn cũ là 8 nên không cập nhật).

Đến M qua C: \(7 + 8 = 15\). Ta có nhãn tạm thời cho M là [15, C].

Trong các nhãn tạm thời (B: 8, M: 15), số 8 là nhỏ nhất, ta chọn B làm đỉnh vĩnh viễn tiếp theo.

Bước 3: Từ đỉnh vĩnh viễn B

Xét các đỉnh kề B chưa có nhãn vĩnh viễn là N và M.

Đến N qua B: \(8 + 9 = 17\). Nhãn tạm thời cho N là [17, B].

Đến M qua B: \(8 + 8 = 16\) (lớn hơn nhãn cũ là 15 nên không cập nhật).

Trong các nhãn tạm thời (N: 17, M: 15), số 15 là nhỏ nhất, ta chọn M làm đỉnh vĩnh viễn.

Bước 4: Từ đỉnh vĩnh viễn M

Xét các đỉnh kề M chưa có nhãn vĩnh viễn là N và P.

Đến N qua M: \(15 + 6 = 21\) (lớn hơn nhãn cũ là 17 nên không cập nhật).

Đến P qua M: \(15 + 6 = 21\). Nhãn tạm thời cho P là [21, M].

So sánh các nhãn tạm thời còn lại (N: 17, P: 21), ta chọn N làm đỉnh vĩnh viễn.

Bước 5: Từ đỉnh vĩnh viễn N

Đến P qua N: \(17 + 10 = 27\) (lớn hơn nhãn cũ là 21 nên không cập nhật).

Cuối cùng, đỉnh P nhận nhãn vĩnh viễn là [21, M].

Kết luận:

Đường đi ngắn nhất có độ dài là 21.

Truy ngược từ nhãn: \(P \leftarrow M \leftarrow C \leftarrow A\).

Lộ trình: A → C → M → P.

Đáp án: 21