Dijkstra và Bellman-Ford tìm đường đi ngắn nhất như thế nào?

Question

Accepted Answer

Cả hai đều tìm **đường đi ngắn nhất từ một nguồn** trong một đồ thị có trọng số. **Dijkstra** nhanh hơn nhưng cần trọng số **không âm**; **Bellman-Ford** chậm hơn nhưng xử lý được các cạnh **âm** và phát hiện chu trình âm.

## Dijkstra (greedy + min-heap)

Liên tục mở rộng nút chưa thăm gần nhất và nới lỏng (relax) các đỉnh kề của nó.

```python
import heapq

def dijkstra(graph, src):
    dist = {n: float('inf') for n in graph}
    dist[src] = 0
    pq = [(0, src)]                    # (khoảng cách, nút)
    while pq:
        d, u = heapq.heappop(pq)       # gần nhất trước
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if d + w < dist[v]:        # nới lỏng cạnh
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist
```

## Bellman-Ford (nới lỏng kiểu DP)

Nới lỏng **tất cả** các cạnh V-1 lần; một lần nới lỏng thêm nữa nghĩa là có chu trình âm.

## So sánh

| | Dijkstra | Bellman-Ford |
|---|---------|--------------|
| Trọng số | không âm | bất kỳ (kể cả âm) |
| Thời gian | O((V+E) log V) | O(V·E) |
| Chu trình âm | không áp dụng | phát hiện được |

## Khi nào dùng / những cạm bẫy

Dùng **Dijkstra** theo mặc định cho trọng số không âm (bản đồ, mạng). Dùng **Bellman-Ford** khi tồn tại cạnh âm (ví dụ kinh doanh chênh lệch giá - arbitrage). Dijkstra âm thầm hỏng trên trọng số âm — một cái bẫy kinh điển.

## Tại sao điều này quan trọng

Các thuật toán đường đi ngắn nhất vận hành định tuyến, dẫn đường, các giao thức mạng, và phân tích chi phí phụ thuộc.

Biết ràng buộc trọng-số-không-âm của Dijkstra giúp ngăn các đáp án sai trong thực tế.

Ý tưởng nới lỏng kết nối tư duy greedy và DP, khiến nó trở thành một chủ đề phong phú ở cấp độ senior.

	Dijkstra	Bellman-Ford
Trọng số	không âm	bất kỳ (kể cả âm)
Thời gian	O((V+E) log V)	O(V·E)
Chu trình âm	không áp dụng	phát hiện được