bài tập trắc nghiệm ề bài toán đường đi ngắn nhất một nguồn (SPP

Trong thuật toán Dijkstra, nếu có một đỉnh với trọng số cạnh âm, điều gì sẽ xảy ra?

• A. Thuật toán vẫn hoạt động bình thường.

• B. Thuật toán sẽ không hoạt động chính xác.

• C. Thuật toán sẽ chạy vô hạn.

• D. Thuật toán sẽ bỏ qua cạnh đó.

Điều kiện cần để thuật toán Dijkstra có thể áp dụng hiệu quả là gì?

• A. Đồ thị phải có cạnh trọng số dương.

• B. Đồ thị phải là đồ thị vô hướng.

• C. Đồ thị phải có một số đỉnh lẻ.

• D. Đồ thị phải là đồ thị đầy đủ.

Trong thuật toán Dijkstra, điều gì sẽ xảy ra nếu tất cả các trọng số cạnh đều tăng thêm một giá trị không âm?

• A. Đường đi ngắn nhất giữa các đỉnh vẫn không đổi

• B. Đường đi ngắn nhất có thể thay đổi

• C. Thuật toán sẽ chạy lâu hơn

• D. Kết quả của thuật toán sẽ sai

Đối với đồ thị trọng số, khi nào một thuật toán tìm kiếm đường đi ngắn nhất cần phải kiểm tra tất cả các cạnh của đồ thị?

• A. Khi đồ thị có chu trình trọng số dương

• B. Khi đồ thị có trọng số âm

• C. Khi đồ thị là đồ thị đầy đủ

• D. Khi đồ thị có trọng số dương

Nếu đỉnh đích không thể đạt được từ đỉnh nguồn trong thuật toán Dijkstra, giá trị khoảng cách cuối cùng cho đỉnh đích sẽ là gì?

• A. 0

• B. Vô cực (∞)

• C. Giá trị ngẫu nhiên

• D. Giá trị âm

Trong đồ thị có cạnh trọng số dương, điều gì xảy ra với đường đi ngắn nhất từ đỉnh nguồn đến một đỉnh nếu trọng số tất cả các cạnh được tăng thêm một giá trị dương không âm?

• A. Đường đi ngắn nhất sẽ không thay đổi

• B. Đường đi ngắn nhất sẽ thay đổi

• C. Đường đi ngắn nhất sẽ trở thành vô cực  (∞)

• D. Đường đi ngắn nhất sẽ trở thành giá trị âm