Mô phỏng thuật toán Phát hiện chu trình âm

Negative Cycle Detection · Nhóm: Đồ thị

Phát hiện chu trình âm (Negative Cycle Detection), nhóm Đồ thị.

Mã Python

def find_negative_cycle(edges, V):
    dist = [0] * V
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    # V-th relaxation pass
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return True   # still relaxing: negative cycle
    return False

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.