Đường đi ngắn nhất

Thuật toán nào sau đây không thể xử lý đồ thị có cạnh trọng số âm?

• Bellman–Ford

• Dijkstra

• SPFA

• Floyd–Warshall

Độ phức tạp thời gian trung bình của thuật toán Dijkstra trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

• O (V²)

• O(E + VlogV)

• O(ElogV)

• O(VE)

Bellman–Ford lặp tối đa bao nhiêu lần qua tất cả các cạnh để tìm đường đi ngắn nhất trong đồ thị có V đỉnh?

• V lần

• V−1 lần

• E lần

• E−1 lần

Trong thuật toán Dijkstra, nếu bạn khởi tạo tất cả khoảng cách từ đỉnh nguồn bằng vô cực và đỉnh nguồn bằng 0, thì tại bước nào giá trị khoảng cách của một đỉnh mới được “cố định” (không còn thay đổi nữa)?

• Khi đỉnh đó được đưa ra khỏi hàng đợi ưu tiên lần đầu

• Khi mọi cạnh tới nó đã được thả qua

• Khi tất cả các đỉnh khác đã được xử lý

• Khi duyệt hết toàn bộ đồ thị

Thuật toán nào sau đây có thể vừa phát hiện chu trình âm trong đồ thị vừa tìm đường đi ngắn nhất từ một nguồn?

• Dijkstra với kiểm tra dấu hiệu cạnh âm

• Bellman–Ford

• Floyd–Warshall với biến thể phát hiện chu trình

• SPFA không kèm kiểm soát

Trong thuật toán Dijkstra, điều kiện nào sau đây phải đúng để thuật toán hoạt động chính xác?

• Đồ thị phải vô hướng và không có cạnh nào có trọng số âm

• Đồ thị có thể có cạnh âm nhưng không có chu trình âm

• Đồ thị phải có ít nhất một cạnh âm

• Đồ thị bắt buộc phải kết nối đầy đủ

Bellman–Ford sẽ phát hiện chu trình âm bằng cách nào?

• So sánh dist[] trước và sau mỗi vòng lặp, nếu không đổi là có chu trình âm

• Chạy thêm một vòng “relax all edges”; nếu còn cập nhật được, tức tồn tại chu trình âm

• Đếm số cạnh âm; nếu ≥ V thì có chu trình âm

• Kiểm tra xem tổng trọng số đường đi ngắn nhất có âm hay không

Trong Dijkstra (với heap nhị phân), thao tác “decrease-key” (giảm khóa) thường xuất hiện khi nào?

• Khi một đỉnh được đưa vào heap lần đầu

• Khi tìm thấy đường đi ngắn hơn tới một đỉnh đã có trong heap

• Khi loại bỏ đỉnh có khoảng cách nhỏ nhất ra khỏi heap

• Khi in ra đường đi ngắn nhất cuối cùng

Trong trường hợp nào Dijkstra sẽ cho kết quả sai so với Bellman–Ford?

• Đồ thị có nhiều đường song song giữa hai đỉnh

• Đồ thị có cạnh âm nhưng không có chu trình âm

• Đồ thị chỉ có cạnh trọng số dương

• Đồ thị hoàn toàn liên thông

Thuật toán nào sau đây bạn nên chọn khi cần tìm đường đi ngắn nhất từ một nguồn trên đồ thị có thể có cạnh âm?

• Dijkstra với heap Fibonacci

• Bellman–Ford

• A* với heuristic bất kỳ

• BFS