thuyduong2007
Member
Đúng rồi. Do cách hiểu của t là reachable có nghĩa là khi cái đỉnh đó được lấy từ trong heap ra.reachable đầu tiên chưa chắc là ngắn nhất bác, đỉnh nào phải là được chọn để đi tiếp mới là ngắn nhất chứ ạ
Nhưng mà phải nói như thím mới đúng.
Không được đâu, vì theo đề bài thì đồ thị là có hướng, đường đi ở hai chiều không nhất thiết tương đương.
--
Edited: Nếu dùng với đồ thị ngược của input thì có khi được.
Vậy thuật toán sẽ là như này:
- B1: đặt E' = <đảo chiều các cạnh của E>
- B2: Chạy Dijkstra (V, E') với bắt đầu là t. Dừng khi tìm được đường đi ngắn nhất đến tất cả N điểm nguồn,
- B3: Output 3 đường đi ngắn nhất trong số N
T nói là đi ngược lại mà,
.Mà không cần phải tìm ra tất cả N điểm đâu. Chỉ cần đảm bảo số điểm có shortest path đã tìm được + số điểm add thêm vào heap = 3 như đề bài là được. Vì yêu cầu chỉ cần tìm 3 thôi.


