Thuật toán Dijkstra tìm đường đi ngắn nhất đồ thị có trọng số

Mục tiêu kiến thức

• Triển khai thuật toán Dijkstra sử dụng hàng đợi ưu tiên heapq đạt độ phức tạp O((V + E) log V).
• Truy vết đường đi ngắn nhất từ đỉnh nguồn đến toàn bộ các đỉnh khác bằng mảng prev.
• Xử lý các đỉnh không thể đến được (khoảng cách vô cực float('inf') và đường đi []).
• Kiểm tra hợp lệ: raise ValueError nếu phát hiện cạnh có trọng số âm.

Mô tả bài toán

Cho đồ thị có hướng gồm n đỉnh (được đánh số từ 0 đến n - 1) và danh sách các cạnh edges dạng (u, v, w) biểu thị cạnh từ u → v có trọng số w.

Viết hàm dijkstra_shortest_path(n: int, edges: list[tuple[int, int, int]], source: int) -> tuple[list[int | float], dict[int, list[int]]]:

• Kiểm tra trọng số: nếu có bất kỳ cạnh nào có trọng số w < 0, raise ValueError("Trong so canh khong duoc am").
• Tính khoảng cách ngắn nhất từ đỉnh source đến tất cả các đỉnh từ 0 đến n - 1.
• Tái tạo đường đi ngắn nhất chi tiết:
• Với mỗi đỉnh i, paths[i] là danh sách các đỉnh từ source đến i (ví dụ [source, ..., i]).
• Riêng paths[source] = [source].
• Nếu đỉnh i không thể đến được từ source, khoảng cách là float('inf') và paths[i] = [].

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.