Giả sử cho một đồ thị vô hướng có trọng số, cần tìm đường đi chi phí đi lại tối thiểu từ một đỉnh đến đỉnh khác. Chi phí đi lại tính như sau: giả sử đường đi từ A đến C là A→B→C. Chi phí A→B là 10, B→C là 20. Chi phí A→C sẽ là (chi phí A→B) + (chi phí B→C - chi phí tích lũy đến B) = 10 + (20 - 10) = 20. Ta phải tìm chi phí đi lại tối thiểu từ đỉnh có giá trị nhỏ nhất đến đỉnh có giá trị lớn nhất.
Ví dụ, với đầu vào như hình minh họa, đầu ra sẽ là 15.
Có hai đường đi giữa đỉnh 1 và 4. Đường tối ưu là 1→2→4, chi phí = 10 + (15 - 10) = 15. Đường kia chi phí 20.
Giải pháp
Để giải quyết bài toán này, ta thực hiện các bước sau:
- adjList := map mới chứa danh sách rỗng
- Với mỗi item trong edges:
- u := item[0], v := item[1], w := item[2]
- Thêm (w,v) vào adjList[u], thêm (w,u) vào adjList[v]
- q := heap mới, v_list := tập hợp mới
- Thêm (0,1) vào q, flag := True
- Khi q không rỗng:
- c := pop phần tử nhỏ nhất từ q
- Nếu c[1] trong v_list: tiếp tục
- Thêm c[1] vào v_list
- Nếu c[1] == n: flag := False; trả về c[0]
- Với mỗi u trong adjList[c[1]]:
- Nếu u[1] không trong v_list:
- out := max(u[0], c[0], u[1])
- Push out vào heap q
- Nếu u[1] không trong v_list:
- Nếu flag là True: trả về -1
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
from collections import defaultdict
import heapq
def solve(n, edges):
adjList = defaultdict(list)
for item in edges:
u, v, w = map(int, item)
adjList[u].append((w, v))
adjList[v].append((w, u))
q = []
v_list = set()
q.append((0, 1))
flag = True
while q:
c = heapq.heappop(q)
if c[1] in v_list:
continue
v_list.add(c[1])
if c[1] == n:
flag = False
return c[0]
for u in adjList[c[1]]:
if u[1] not in v_list:
out = (max(u[0], c[0]), u[1])
heapq.heappush(q, out)
if flag:
return -1
print(solve(4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)]))
Đầu vào
4, [(1, 2, 10), (2, 3, 5), (2, 4, 15), (1, 4, 20)]
Đầu ra
15