QUIZ CHƯƠNG 8

Thuật toán Bellman-Ford cập nhật khoảng cách tối đa bao nhiêu lần?

• E lần

• V + 1 lần

• V – 1 lần

• V² lần

Dijkstra sẽ cho kết quả sai nếu:

• Đồ thị có chu trình

• Có đỉnh không liên thông

• Có cạnh âm

• Có cạnh bằng 0

Độ phức tạp của Bellman-Ford là:

• O(V + E)

• O(VE)

• O((V + E) log V)

• O(V² log V)

Dijkstra sử dụng cấu trúc dữ liệu nào để tìm đỉnh gần nhất chưa thăm?

• Stack

• Priority Queue

• Queue thường

• Set

Khi chạy Dijkstra, bước đầu tiên là:

• Gán vô hạn cho tất cả các đỉnh, trừ đỉnh bắt đầu

• Chọn đỉnh xa nhất

• Xác định các chu trình

• Sắp xếp danh sách cạnh

Bellman-Ford có thể phát hiện chu trình âm bằng cách:

• Dựa vào độ lớn cạnh âm

• Kiểm tra cập nhật sau lần lặp thứ V–1

• So sánh với Dijkstra

• Xóa hết các cạnh âm

Nếu Bellman-Ford phát hiện chu trình âm, điều đó nghĩa là:

• Đồ thị không liên thông

• Có thể lặp vô hạn tạo đường đi ngắn hơn

• Không có đường đi

• Có đỉnh không có cạnh

Đồ thị có trọng số âm nhưng không có chu trình âm, ta nên dùng:

• Dijkstra

• BFS

• Bellman-Ford

• Prim

Thuật toán Dijkstra dùng để:

• Tìm chu trình Hamilton

• Tìm đường đi dài nhất

• Tìm cây khung nhỏ nhất

• Tìm đường đi ngắn nhất từ 1 đỉnh đến các đỉnh còn lại

Bellman-Ford có thể dùng cho:

• Đồ thị có cạnh âm

• Đồ thị không trọng số

• Đồ thị vô hướng

• Đồ thị không liên thông