Thuật toán Bellman-Ford

def bellman_ford(n, canh_co_huong, src):
    """
    Tìm đường ngắn nhất từ src đến tất cả đỉnh.

    canh_co_huong: [(u, v, w)] — cạnh có hướng từ u đến v, trọng số w
    Trả về (dist[], co_chu_trinh_am)
    """
    INF  = float('inf')
    dist = [INF] * n
    dist[src] = 0

    # V-1 vòng relax toàn bộ cạnh
    for _ in range(n - 1):
        cap_nhat = False
        for u, v, w in canh_co_huong:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                cap_nhat = True
        if not cap_nhat:    # Tối ưu: dừng sớm nếu không còn cập nhật
            break

    # Kiểm tra chu trình âm: vòng thứ V vẫn relax được → có chu trình âm
    for u, v, w in canh_co_huong:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return dist, True

    return dist, False


# Ví dụ không có chu trình âm
canh = [(0,1,1),(0,2,4),(1,2,3),(1,3,-2),(2,3,2)]
dist, cycle = bellman_ford(4, canh, src=0)
print("Khoảng cách:", dist)      # [0, 1, 4, -1]
print("Chu trình âm:", cycle)    # False

# Ví dụ có chu trình âm: 1→2→3→1 tổng trọng số = -1
canh2 = [(0,1,0),(1,2,1),(2,3,-2),(3,1,0)]
_, cycle2 = bellman_ford(4, canh2, src=0)
print("Chu trình âm:", cycle2)   # True

def bellman_ford_voi_duong_di(n, canh, src):
    """Bellman-Ford kèm truy vết đường đi."""
    INF  = float('inf')
    dist = [INF] * n
    prev = [-1]  * n
    dist[src] = 0

    for _ in range(n - 1):
        for u, v, w in canh:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u

    def lay_duong_di(dst):
        if dist[dst] == INF:
            return None   # Không tới được
        path, cur = [], dst
        while cur != -1:
            path.append(cur)
            cur = prev[cur]
        return path[::-1]

    return dist, lay_duong_di

canh = [(0,1,1),(0,2,4),(1,2,3),(1,3,-2),(2,3,2)]
dist, get_path = bellman_ford_voi_duong_di(4, canh, src=0)
print(f"0→3: {dist[3]}, đường đi: {get_path(3)}")   # -1, [0, 1, 3]

def co_chu_trinh_am(n, canh):
    """Kiểm tra đồ thị có hướng có chu trình âm không (bắt đầu từ mọi nguồn)."""
    INF  = float('inf')
    dist = [0] * n     # Trick: khởi tạo 0 ≡ thêm một siêu nguồn kết nối tất cả

    for _ in range(n - 1):
        for u, v, w in canh:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    for u, v, w in canh:
        if dist[u] + w < dist[v]:
            return True
    return False

canh1 = [(0,1,1),(1,2,2),(2,0,-4)]    # Chu trình âm: 0+1+2-4 = -1
canh2 = [(0,1,1),(1,2,2),(2,0,-2)]    # Chu trình không âm: 0+1+2-2 = 1
print(co_chu_trinh_am(3, canh1))   # True
print(co_chu_trinh_am(3, canh2))   # False

def duong_ngan_nhat_toi_da_k_canh(n, canh, src, dst, k):
    """
    Tìm đường đi ngắn nhất từ src đến dst, sử dụng tối đa k cạnh.
    Biến thể của Bellman-Ford: chỉ chạy k vòng.
    """
    INF   = float('inf')
    prev  = [INF] * n
    prev[src] = 0

    for _ in range(k):
        curr = prev[:]
        for u, v, w in canh:
            if prev[u] != INF and prev[u] + w < curr[v]:
                curr[v] = prev[u] + w
        prev = curr

    return prev[dst] if prev[dst] != INF else -1

# Bay từ 0→3, tối đa 2 chặng
canh = [(0,1,100),(0,2,500),(1,2,100),(1,3,600),(2,3,200)]
print(duong_ngan_nhat_toi_da_k_canh(4, canh, 0, 3, 2))   # 700 (0→1→3 hoặc 0→2→3 không phải vì cần 2 cạnh)
print(duong_ngan_nhat_toi_da_k_canh(4, canh, 0, 3, 1))   # 600 (0→1→3 dùng 2 cạnh nhưng k=1 thì chỉ 1 cạnh)

import math

def co_co_hoi_kinh_doanh(n, ty_gia):
    """
    Kiểm tra có thể đổi tiền lòng vòng để kiếm lời không.
    ty_gia[i][j] = tỷ giá quy đổi từ đồng i sang đồng j.
    Kiếm lời = tích tỷ giá > 1 = chu trình âm trong đồ thị log.

    Biến đổi: log(product) > 0 ↔ sum(-log) < 0 ↔ chu trình âm với trọng số -log.
    """
    canh = []
    for i in range(n):
        for j in range(n):
            if ty_gia[i][j] > 0:
                # Đổi product > 1 thành sum < 0 bằng -log
                canh.append((i, j, -math.log(ty_gia[i][j])))

    dist = [0.0] * n
    for _ in range(n - 1):
        for u, v, w in canh:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    for u, v, w in canh:
        if dist[u] + w < dist[v] - 1e-9:
            return True
    return False

# Ví dụ: USD, EUR, GBP
# USD→EUR→GBP→USD = 1.2 × 0.9 × 1.1 = 1.188 > 1 → kiếm lời được
ty_gia = [
    [1.0, 1.2, 0.8],
    [0.85, 1.0, 0.9],
    [1.25, 1.1, 1.0]
]
print(co_co_hoi_kinh_doanh(3, ty_gia))   # True hoặc False tùy tỷ giá