Bài toán: cho đồ thị vô hướng N đỉnh, M cạnh và không có chu trình âm. Trong các đường đi đơn từ đỉnh S đến T, chỉ ra đường đi có trọng số nhỏ thứ k.
Mình mới biết thuật toán O(K*N^3) cho bài toán này. Ai có thuật toán tốt hơn thì share cho mình nhé!

Theo mình thì bài này có một cách O(K * (N^2 + M))

Như nào vậy bạn?

Nếu chấp nhận chu trình thì có thể làm trong O(m+nlogn+k).

Nếu là đường đi đơn giản trên đồ thị tổng quát: trên đồ thị có hướng, thuật toán Yen thực hiện ở độ phức tạp O(kn(m+n log n)), còn trên đồ thị vô hướng, độ phức tạp là O(k(m+n log n)).
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.15.3724&rep=rep1&type=pdf

Nếu là đường đi cho phép lặp đỉnh thì bài toán trở nên khá đơn giản rồi, dijkstra heap + cấu trúc dữ liệu hoặc là A*.
Nếu là đường đi không cho phép lặp đỉnh thì bài toán sẽ khó hơn rất nhiều (mình nghĩ thế có lẽ vì mình chưa nghĩ ra). Nghe nói có thể giải bằng Ford Bellman Queue vòng hoặc là dựng cây đường đi ngắn nhất sau đó quy hoạch động trên cây này (theo ý tưởng của anh Quỳnh - ĐH Công nghệ).

Thân ái,
HY TRƯỜNG SƠN

Tái bút: Mà quên mất chưa hỏi rõ bạn Tuấn Anh Ninh Bình là bài này là "K Shortest Paths" or "K Longest Paths" vì bạn ghi ở trên là đường đi dài thứ k.

Cách của mình nói cặn kẽ thì hơi dài dòng. Nhưng cơ bản là thế này, đầu tiên ta cực tiểu hóa các đường đi ngắn nhất từ S tới các đỉnh, rồi cực tiểu hóa các đường đi ngắn nhì, ... cuối cùng cực tiểu hóa đường đi ngắn thứ k.
- Bước 1: cực tiểu hóa đường đi ngắn nhất thì đơn giản
- Bước 2: cực tiểu hóa đường đi ngắn nhì: trước hết fải update các d[2, u] từ các d[1, v] (trong đó d[i, j] là đường đi ngắn thứ i từ S -> j, (u, v) là một cạnh nhưng lưu ý không update từ những d[1, v] thuộc đường đi ngắn nhất của d[1, u]). Sau đó Dijk giữa các d[2] như bình thường.
- Bước 3: update các d[3] giống như bước 2 từ các d[1, v] và d[2, v]. Nếu xử lí khéo kiểu cộng dồn thì có thể chỉ cần update từ d[2, v]. Dijk giữa các d[3].
* Như vậy ta mất K bước, mỗi bước mất một lần update mất M và một lần Dijk mất (NlogN + M) -> ĐPT là O(K*(NlogN + M)). Không biết là có giống cách trong tài liệu trên không?

Có thể dùng cấu trúc dữ liệu để tối ưu hơn nữa hoặc là có thể dùng thêm A* (N,K<=10000 vẫn ok, theo ý tưởng của anh Nguyễn Duy Khương)

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ả =.=

cách củae lightning cũng ổn đó.Tuấn anh xài thử xem em