Chỉ giúp mình thuật toán tìm đường đi

[sparrow]

Mấy bạn chỉ giúp mình làm sao liệt kê hết tất cả các đường đi từ đỉnh A đến đỉnh B trong một đồ thị. Mình phải sử dụng thuật toán nào bây giờ?
Mấy bạn chỉ mình sớm sớm với. Nếu có code rồi thì cho mình xin luôn với.
Cám ơn mấy bạn nhiều.

[minh chau]

Thường để tìm đường đi người ta thường nghĩ đến thuật toán "backtracking".Nói nôm na là lần từng bước nếu thấy thỏa và khi gặp điều kiện không thỏa thì gỡ bước đi đó và quay trở lại bước đi trước!!Đầu tiên bạn phải làm một hàm xuất để xuất ra điều kiện khi đã thỏa mãn bài...Sau đó khai báo một hàm mảng có thể là 2 chiều hoặc 1 chiều để chứa giá trị,hoặc tọa độ của mỗi đỉnh(đó có thể là tọa dộ đường đi bạn muốn in ra khi đã tìm thấy đường đi từ A -> B),một hàm boolean để xét tại vị trí đó đã đi qua hay chưa,......
If đỉnh đó chưa đi qua và tọa dộ tại đó thỏa 1 điều kiện nào đó Thì
bạn sẽ gán lại là đỉnh đó bằng true(đã đi qua), các thao tác khác tùy vào chương trình của bạn
sau đó gọi lại đệ qui hàm này để xét vị trí mới.Sau khi đã đi hết mảng thì
gán lại bằng false,gở bỏ các giá trị đã xét theo thứ tự ngược trở lại để xét xem còn đường nào khác nữa không..........Cứ như vậy!!!Chúc bạn thành công

[StarGhost]

Ặc ặc, chưa bao giờ thấy ai hỏi vấn đề này. Bạn làm gì mà phải liệt kê hết vậy. Như thế lưu trữ sẽ tốn lắm đó.

[thanh dat]

Thường thì hay có bài toán tìm đường đi ngắn nhất , có thể dùng thuật toán Dijkstra để giải quyết vấn đề này , còn muốn liệt kê hết thì đúng là dùng cách "quay lui" là ổn .

[tommyle]

Cái bạn đang hỏi có thể là về Graph Algorithms. Có 2 cái phổ biến nhất đó là Dijkstra's algorithm (shortest-paths problem) and Prim's algorithm (minimum-cost spanning tree problem). Bạn Google 2 cái algorithms này nha... ;)

[songok]

Neu chi duyet duong di don thuan nhu ban noi thi chi can 2 thuat toan dfs va bfs la du, dfs cai theo kieu de quy ( nen so dinh lon chac se bi tran ) bfs thi cai theo queue.
Ngoai ra thuat toan Warshall voi do phuc tap 0(nx3) se cho ra duong di ngan nhat cua tat cac moi dinh voi nhau

[netwalker]

trong cuốn "lý thuyết đồ thị" cuả Nguyễn Cam (vài ai nữa) có chỉ rất rõ 2 giải thuật Dijkstra và Prim
riêng mình thích prim hơn, xây dựng nó đơn giản :)

[thailehuy]

Liệt kê hết hả ? Chắc chết luôn đó, một đồ thị 8 cạnh là có mấy ngàn cách đi rồi. Còn điều kiện này kia nọ nữa chứ.

Tìm đường ngắn nhất thì may ra

[netwalker]

hoàn toàn có thể liệt kê hết
ta dùng hàng đợi :)

[hoabanglangtim]

Xin chào các bác ! Tui cũng gặp một vấn đề như vậy. Cụ thể là để tìm cặp đường đi ngắn nhất nối giữa 2 đỉnh( với giả thiết rằng luôn có cặp đường đi). Các bác cho tui hướng giải quyết đi . Cam ơn các bác trước.

[VSiAQ]

Hic. Nếu mình không nhầm thì Prim là thuật toán tìm cây khung nhỏ nhất (minimum spanning tree) chứ đâu phải đường đi ngắn nhất. Đường đi ngắn nhất là Dijkstra và Floy thì đúng hơn...

[netwalker]

@VSiAQ: sorry, lộn tùm lum :)
@hoabanglangtim

Đường đi ngắn nhất là Dijkstra và Floy thì đúng hơn...

[ngọa hổ]

mọi người ai biết thì giảng chi tiết đi được không, kiếm google ra toàn mấy cái thuật toán vớ vẩn gì thôi, với lại nó còn viết tiếng anh + dùng luôn cho java chứ không nói kỹ, là hoạt động như thế nào. em nghe nói là cái này nó còn có node, goal point, h point nữa

[quangtq]

Bài này quay lui đi


Thủ tục try(đỉnh u)
{
free[u]=false;
Duyệt v từ 1->n nếu có cạnh nối (u,v) và free[v]=true (v chưa đi qua) thì
{ trace[v]=u; if v=Đỉnh B thì In kết quả, truy vết theo mảng Trace, ngược lại { trace[v]:=u; free[v]=false; try(v); free[v]:=true; }
}

Mình dùng mã giả vì ko biết bạn viết trên ngôn ngữ gì

[cap xuan thao]

ai co pro bai toan tim duong di ngan nhat giụa cac dinh tren do thi thi code len cho minh voi
thanks

[=========> Bổ sung bài viết <=========]

cac bac oi cho minh hoi minh muon chay tren c++ ma khi ctrl f9 thi no bao la thieu " iostream"
khac phuc nhu the nao mong cac bac chi giao
thanks

[B&W]

Thuật toán về đồ thị thì ngâm cứu thử slide này xem:
http://www.mediafire.com/download.php?im5n2n1yz5l


cac bac oi cho minh hoi minh muon chay tren c++ ma khi ctrl f9 thi no bao la thieu " iostream"
khac phuc nhu the nao mong cac bac chi giao
thanks
thêm dòng này vào đầu code:
#include <iostream.h>

[coeyadaica]

Àh mình cũng đang cần code C++ của bài toán này mong các bạn giúp đỡ. Vì đề cho là tìm đường đi ngắn thứ 3,4,5 (nếu có), và tìm đường đi dài nhất ko chu trình. Thế nên cho mình xin cái code vét cạn đường đi nhé thanks.