JavaScript is required

Cho mô hình đồ thị biểu diễn sự kết nối và chi phí kết nối giữa các router như hình minh họa bên dưới. Dùng thuật toán Dijkstra để xác định đường đi ngắn nhất từ đỉnh u đến các đỉnh còn lại.

Sau bước 0 (khởi tạo) thì D(v), D(w), D(x), D(y), D(z) có giá trị lần lượt là?

A.

2, 4, 5, ∞, ∞

B.

5, 6, ∞, ∞, 1

C.

∞, 6, 1, 5, ∞

D.

∞,∞,∞,1,5

Trả lời:

Đáp án đúng: A


Thuật toán Dijkstra là thuật toán tìm đường đi ngắn nhất từ một đỉnh nguồn tới tất cả các đỉnh còn lại trong một đồ thị có trọng số không âm. Bước 0 là bước khởi tạo, nơi chúng ta gán khoảng cách ban đầu cho tất cả các đỉnh. Đỉnh nguồn (ở đây là 'u') sẽ có khoảng cách là 0. Tất cả các đỉnh khác sẽ có khoảng cách ban đầu là vô cùng (∞) vì chúng ta chưa tìm được đường đi nào tới chúng. Riêng với đỉnh 'v', có một cạnh nối trực tiếp từ 'u' với trọng số là 2, nên khoảng cách ban đầu từ 'u' đến 'v' được cập nhật là 2. Tương tự, đỉnh 'w' có cạnh nối trực tiếp từ 'u' với trọng số là 4, nên khoảng cách ban đầu từ 'u' đến 'w' là 4. Đỉnh 'x' có cạnh nối trực tiếp từ 'u' với trọng số là 5, nên khoảng cách ban đầu từ 'u' đến 'x' là 5. Các đỉnh 'y' và 'z' không có cạnh nối trực tiếp với 'u', do đó khoảng cách ban đầu của chúng là vô cùng (∞). Vậy, sau bước 0, giá trị D(v), D(w), D(x), D(y), D(z) lần lượt là 2, 4, 5, ∞, ∞.

Tài liệu đề thi cuối kỳ môn Mạng Máy Tính của Đại học Công nghệ Thông tin, ĐHQG TP.HCM. Bao gồm các câu hỏi trắc nghiệm về kiến thức mạng máy tính, giao thức, định tuyến, địa chỉ IP và cấu hình mạng.


40 câu hỏi 75 phút

Câu hỏi liên quan