Chủ đề này có 5 trả lời

[newwave]

Em có một đồ thị có hướng, không trọng số. Em muốn tìm tất cả các đường đi ngắn nhất từ đỉnh đầu đến đỉnh cuối của đồ thị (đỉnh đầu của đồ thị này không có cung nào đi vào, đỉnh cuối thì không có cung nào đi ra). Mong mọi người giúp đỡ, đưa ra giải thuật hoặc giả mã. Em cảm ơn nhiều.

Sau đây là ví dụ về một đồ thị như thế

0->1, 0->2, 1->2, 1->3, 2->3, 2->4, 3->4, 3->5, 4->5

Tìm tất cả đường đi ngắn nhất (đường đi có độ dài 3) từ đỉnh 0 tới đỉnh 5.

Em cảm ơn trước

[smalteagle]

Theo mình thì nên làm thế này :
Trước hết bạn duyệt tìm đỉnh đầu và đỉnh cuối của đồ thị (việc này không khó).
Do đồ thị không có trọng số nên từ đỉnh đầu, bạn dùng thuật toán BFS (Breadth First Search) duyệt qua đồ thị. Ứng với mỗi đỉnh, bạn sẽ tìm được đường đi ngắn nhất từ đỉnh đầu đến đỉnh đó. Khi đó bạn sẽ biết được đường đi ngắn nhất từ đỉnh đầu đến đỉnh cuối là bao nhiêu (giả sử là k).
Bước tiếp theo bạn duyệt qua tất cả các đỉnh có đường đi ngắn nhất từ đỉnh đầu đến nó là k-1, kiểm tra xem có đường nối từ đỉnh đó đến đỉnh cuối của đồ thị hay không. Nếu có đường nối thì đó là 1 đường đi ngắn nhất -> in ra kết quả hoặc lưu lại kết quả.
Sau khi thực hiện thuật toán như trên, bạn sẽ có tất cả các đường đi ngắn nhất, vì giả sử có một đường đi ngắn nhất nào đó không được in ra, gọi A là điểm trước điểm cuối cùng trong đường đi đó, thì khoảng cách từ điểm đầu đến A không thể bằng k-1 (do nếu bằng k-1 thì đường đi đó đã được in ra theo thuật toán). Nếu khoảng cách này nhỏ hơn k-1 thì đường đi như trên sẽ có chiều dài nhỏ hơn k (mâu thuẫn với kết quả của thuật toán BFS). Nếu khoảng cách này lớn hơn k-1 thì đường đi trên không thể là đường đi ngắn nhất do có chiều dài lớn hơn k. Điều này dẫn đến mâu thuẫn.

[HaiDang]

Cách làm của bạn sai rồi, nếu như lại tìm tất cả các đỉnh mà từ đỉnh đầu đi tới có độ dài là k-1, thế còn k -2, k-3, .., k- k+1 thì sao???
Cách giải trên không hiệu quả, chi phí rất lớn
Cách của tui như thế này:
Gọi A là đỉnh đầu, B là cuối
Thứ nhất bạn sử dụng Dijkstra từ A đến B, thế là bạn đã có 1 mảng luu tất cả đường đi ngắn nhất tử A đến mọi đỉnh trong đồ thị. Sau đó bạn có thể loang về từ B--->A theo DFS hay BFS gì cũng được rồi tìm trên đồ thị những đỉnh v mà d(v,A) + d(v,B) =d(A,B) thì đó là 1 đưìơng đi, sau đó chỉ việc đếm được đi, còn muốn xuất ra đường đi thì chỉ việc lần ngược lại.

[smalteagle]

Cách làm của bạn sai rồi, nếu như lại tìm tất cả các đỉnh mà từ đỉnh đầu đi tới có độ dài là k-1, thế còn k -2, k-3, .., k- k+1 thì sao???
Cách giải trên không hiệu quả, chi phí rất lớn

Trước hết, mình xin nhắc lại rằng đây là một đồ thị có hướng nhưng KHÔNG CÓ TRỌNG SỐ, do đó thuật toán BFS cũng sẽ cho biết độ dài đường đi ngắn nhất từ đỉnh đầu đến tất cả các đỉnh trong đồ thị (tương đương thuật toán Dijkstra, nhưng độ phức tạp nhỏ hơn). Đường đi này chính là số cung ngắn nhất phải đi qua từ đỉnh đầu đến đỉnh đó.
Thuật toán của mình không xét các đỉnh có độ dài đường đi từ đỉnh đầu tới nó là k-2,k-3... vì chắc chắn các đỉnh này không thể có đường đi trực tiếp từ nó đến đỉnh cuối. Bởi vì nếu có một đường đi như vậy, thì đường đi ngắn nhất từ đỉnh đầu đến đỉnh cuối phải nhỏ hơn k, điều này mâu thuẫn với kết quả thuật toán BFS, vì theo thuật toán BFS đã thực hiện, kết quả cho ta đường đi ngắn nhất phải là k.
Chi phí thực hiện của thuật toán mình đưa ra trên thực tế cũng không lớn. Nếu tính tổng chi phí thì thuật toán BFS và các thuật toán duyệt qua các đỉnh chỉ có độ phức tạp khoảng O(n). Tức là độ phức tạp thuật toán của mình là O(n).
Thuật toán bạn đưa ra hoàn toàn chính xác, và nó là một thuật toán rất tốt trong trường hợp đồ thị đã cho là CÓ TRỌNG SỐ.

[binhminhhesang]

theo em với bài toán có hướng không trọng số ta cứ dùng bfs chắc chắn sẽ được dường đi ngắn nhất không nên phức tạp hóa vấn đề

[newwave]

Thank các anh đã giúp đỡ.

Vì em làm việc trên đồ thị ko có trọng số, nên cách của anh smalteagle có chi phí nhỏ hơn của anh Hải Đăng. Em biết trước điểm đầu điểm cuối nên ko cần phải tìm điểm đầu điểm cuối làm gì.

Trước khi em gửi đăng bài này, em đã làm theo cách anh smalteagle, đã tìm ra k và loang ngược trở lại. Chỉ có điều khi em cài đặt thuật toán thì vấn đề lưu lại đỉnh mà từ đó rẽ nhánh bằng queue thì không thành công (vẫn có chỗ sai, mặc dù phần nhiều trường hợp là đúng). Vì thế em mới nhờ các anh viết giả mã. Bài toán tưởng đơn giản mà em code không được chính xác hoàn toàn. Có lẽ khả năng code của em kém quá.

Dù sao một lần nữa xin cảm ơn sự giúp đỡ của các anh.

Bài viết đã được chỉnh sửa nội dung bởi newwave: 17-04-2006 - 21:08