EternalAutumn viết:
QUOTE:
Anh vanhoa có thể nói rõ hơn cách chấp nhận chu trình được ko ạ?
@Sơn + Tùng: đồ thị ko có chu trình âm chứ vẫn có cạnh trọng số âm mà --> dijk ?
@Sơn: mấy cái em nói chỉ là ý tưởng nhưng thực tế thì nó chả hề đơn giản và dễ hình dung thế nào. Em đã cài thử và ACC được với cách A* chưa? Nếu có thì em nên nói chi tiết là em định làm ntn vì anh thấy biết ý tưởng thế cũng chả có ý nghĩa thực tế gì cả. Đâu phải cứ nói tên người nêu ra ý tưởng là nó chắc chắn đúng và có ý nghĩa :| Nói đơn giản thì nói mỗi ý tưởng thế chả khác gì chém gió cả =.=
@Anh RR: Đúng là em không để ý thật.
Nhưng mà để biến đổi đồ thị về thành đồ thị không có cạnh âm cũng không khó lắm anh ạ.
- Trước hết dùng FordBellMan một lần tính được đường đi ngắn nhất từ S đến các đỉnh còn lại gọi đường đi đó là c[i].
- Với mỗi cạnh (u, v) có trọng số cost[u, v] ta thay cost[u, v] bằng cost[u, v] - c[v] + c[u].
* Nhận xét:
+ ta thấy giữa cost[u, v] >= c[v] - c[u] (với mọi u, v) (vì nếu cost[u, v] < c[v] - c[u] thì c[v] không còn lai đường đi ngắn nhất từ S -> v nữa) => Sau khi biến đổi thì mọi cạnh trong đồ thi đều ko âm.
+ Hơn nữa ta xét một đường đi bất kì từ S -> u bất kì. Giả sử qua A, B, C sẽ bằng: cost[S, A] - c[A] + c[S] + cost[A, B] - c[B] + c[A] + ... + cost[C, u] - c[u] + c[C] = cost[S, A] + cost[A, B] + .. + cost[C, u] + c[S] - c[u] -> Mọi đường từ S -> u sẽ đều tăng thêm một chi phí là c[S] - c[u]. Vậy thứ tự đường ngắn thứ k từ S-> u là không đổi. Sau khi biến đổi trọng số của đồ thị, ta áp dụng thuật toán em nêu ở bài trên là ok. Kết quả chỉ cần trừ đi (c[S] - c[T]) là ổn.
* vậy độ phức tạp vẫn như trên cộng thêm đoạn FOrdBellMan ban đầu thì ĐPT sẽ là: O(n^3 + k(m + nlogn))
Được ưa thích: 0
.
