Trong bài toán tối ưu hóa mạng lưới cung ứng (Supply Chain), tại sao việc sử dụng thuật toán Bellman-Ford lại được ưu tiên hơn Dijkstra khi đồ thị có trọng số âm, và rủi ro hiệu năng nào cần lưu ý trong môi trường Enterprise?

Question

Accepted Answer

Phân tích bản chất
Thuật toán Dijkstra dựa trên cơ chế tham lam (greedy), giả định rằng khi một nút đã được thăm, đường đi ngắn nhất đến nó đã được tìm thấy. Điều này không còn đúng nếu đồ thị chứa cạnh có trọng số âm, vì một đường đi dài hơn về số lượng cạnh có thể có tổng trọng số nhỏ hơn sau khi đi qua cạnh âm.
Tại sao chọn Bellman-Ford

Khả năng xử lý cạnh âm: Bellman-Ford thực hiện nới lỏng (relaxation) tất cả các cạnh V-1 lần, cho phép cập nhật lại khoảng cách ngay cả khi gặp trọng số âm.
Phát hiện chu trình âm: Thuật toán có khả năng phát hiện chu trình âm (negative cycle) bằng cách kiểm tra lần lặp thứ V. Nếu khoảng cách vẫn giảm, nghĩa là tồn tại chu trình âm khiến bài toán không có lời giải tối ưu.

Rủi ro hiệu năng

Độ phức tạp: O(V * E), chậm hơn nhiều so với O((V+E) log V) của Dijkstra.
Giải pháp: Chỉ sử dụng Bellman-Ford khi thực sự cần thiết. Trong hệ thống Enterprise, nếu đồ thị lớn, hãy cân nhắc chuyển đổi trọng số bằng kỹ thuật Johnson's algorithm hoặc kiểm tra tính hợp lệ của dữ liệu đầu vào để loại bỏ cạnh âm nếu không cần thiết.

Ví dụ code minh họa

def bellman_ford(graph, V, src):
    dist = [float('inf')] * V
    dist[src] = 0
    for _ in range(V - 1):
        for u, v, w in graph:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    # Kiểm tra chu trình âm
    for u, v, w in graph:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            raise Exception('Đồ thị chứa chu trình âm')

Trong bài toán tối ưu hóa mạng lưới cung ứng (Supply Chain), tại sao việc sử dụng thuật toán Bellman-Ford lại được ưu tiên hơn Dijkstra khi đồ thị có trọng số âm, và rủi ro hiệu năng nào cần lưu ý trong môi trường Enterprise?

Phân tích bản chất

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi graph theory liên quan cùng chủ đề