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

🎯 Mục tiêu

Luyện tập cài đặt Dijkstra, Bellman-Ford trên đồ thị có trọng số và phát hiện chu trình âm.

Mô tả bài tập

Bài toán đường đi ngắn nhất là một trong những bài toán quan trọng nhất trong lý thuyết đồ thị. Bạn sẽ cài đặt hai thuật toán kinh điển và hiểu khi nào dùng thuật toán nào.

Yêu cầu

Bài 1: Dijkstra với Priority Queue

Cài đặt thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh nguồn đến tất cả các đỉnh khác. Đồ thị có trọng số không âm.

import heapq

def dijkstra(graph: dict[int, list[tuple[int, int]]], src: int) -> dict[int, int]:
    """
    Tìm khoảng cách ngắn nhất từ src đến mọi đỉnh.
    graph[u] = [(v, weight), ...] - danh sách kề có trọng số.
    Trả về dict {đỉnh: khoảng_cách}.
    """
    # TODO: Cài đặt Dijkstra
    pass

graph = {0: [(1,4),(2,1)], 1: [(3,1)], 2: [(1,2),(3,5)], 3: []}
assert dijkstra(graph, 0) == {0: 0, 1: 3, 2: 1, 3: 4}

Bài 2: Bellman-Ford

Cài đặt thuật toán Bellman-Ford cho đồ thị có thể có cạnh trọng số âm.

def bellman_ford(n: int, edges: list[tuple[int,int,int]], src: int) -> dict[int, float]:
    """
    Tìm khoảng cách ngắn nhất từ src. edges = [(u, v, w), ...].
    Trả về dict khoảng cách, giá trị float('inf') nếu không đến được.
    """
    # TODO: Cài đặt Bellman-Ford
    pass

edges = [(0,1,4), (0,2,1), (2,1,2), (1,3,1), (2,3,5)]
assert bellman_ford(4, edges, 0) == {0: 0, 1: 3, 2: 1, 3: 4}

Bài 3: Phát hiện chu trình âm

Mở rộng Bellman-Ford để phát hiện chu trình có tổng trọng số âm.

def has_negative_cycle(n: int, edges: list[tuple[int,int,int]]) -> bool:
    """Kiểm tra đồ thị có chu trình âm không."""
    # TODO: Cài đặt phát hiện chu trình âm
    pass

assert has_negative_cycle(3, [(0,1,1), (1,2,-1), (2,0,-1)]) == True
assert has_negative_cycle(3, [(0,1,1), (1,2,1), (2,0,1)]) == False

Bài 4: Truy vết đường đi

Mở rộng Dijkstra để không chỉ tìm khoảng cách mà còn trả về đường đi cụ thể.

def dijkstra_path(graph: dict, src: int, dst: int) -> tuple[int, list[int]]:
    """Trả về (khoảng_cách, đường_đi) từ src đến dst."""
    # TODO: Cài đặt
    pass

graph = {0: [(1,4),(2,1)], 1: [(3,1)], 2: [(1,2),(3,5)], 3: []}
assert dijkstra_path(graph, 0, 3) == (4, [0, 2, 1, 3])

Phân tích độ phức tạp

Bài	Time	Space
1 - Dijkstra (heap)	O((V + E) log V)	O(V + E)
2 - Bellman-Ford	O(V × E)	O(V)
3 - Chu trình âm	O(V × E)	O(V)
4 - Truy vết đường đi	O((V + E) log V)	O(V + E)

Gợi ý

Gợi ý Bài 1

Dùng heapq với tuple (distance, node). Khi lấy đỉnh từ heap, nếu khoảng cách lớn hơn giá trị đã biết thì bỏ qua (lazy deletion).

Gợi ý Bài 3

Chạy thêm vòng lặp thứ V của Bellman-Ford. Nếu vẫn có cạnh có thể relaxation → tồn tại chu trình âm.

Gợi ý Bài 4

Duy trì mảng prev[v] lưu đỉnh trước v trên đường đi ngắn nhất. Sau khi chạy Dijkstra, truy ngược từ dst về src.

Lời giải tham khảo

Xem lời giải

import heapq
def dijkstra(graph: dict[int, list[tuple[int, int]]], src: int) -> dict[int, int]:
    dist = {node: float('inf') for node in graph}
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return {k: v for k, v in dist.items() if v != float('inf')}
def bellman_ford(n, edges, src):
    dist = {i: float('inf') for i in range(n)}
    dist[src] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist
def has_negative_cycle(n, edges):
    dist = [0] * n
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return True
    return False

📚 Bài liên quan

• Thuật toán Dijkstra
• Thuật toán Bellman-Ford