30/09/2018, 16:55
Hỏi về các thuật toán tìm đường?
Chào mọi người , em là Học .
Hiện tại em đang xem cuốn GT VS LT của thầy lê mình hoàng nhưng đến bài 8 : Bài toán đường ngắn nhất và thầy có trình bày ra 3 phương pháp để làm : Ford Bellman , Dijstra, … thật sự em hơi hoang mang khi đọc vì em ko hiểu bất cứ gì về các phương pháp mà thầy nêu ra . Nên hôm nay em lên đây xin sự trợ giúp của các anh chị cũng như các bạn giúp đỡ giải thích giúp mình vấn đề trên .Cảm ơn các bạn đã quan tâm topic của mình
Chúc các bạn may mắn
Học
Bài liên quan
Lên youtube xem cách biểu diễn các thuật toán đồ thị bằng hình cho dễ hiểu. đọc không khó hiểu lắm. Hoặc đây có hình động nè
http://www.cs.usfca.edu/~galles/visualization/Dijkstra.html
tôi đọc 3 tiếng đồng hồ chả hiểu gì cứ đọc đi đọc lại
Hồi đó mình đọc cũng chẳng hiểu gì, đến bây giờ hiểu rồi cũng chẳng biết giải thích như thế nào. Tìm đường đi ngắn nhất của Dijkstra cũng là phương pháp quy hoạch động.
Mình chỉ có code cho bạn thôi.
Đọc xuông thì s hiểu đc ‘3’
Phải lấy giấy ra, vẽ đồ thị và debug từng dòng code thì mới thấm
Ko có code luôn @@ toàn chữ với chữ
Nhìn vào cái ảnh động mà a @Rok_Hoang post thì mình nhớ ra thế này:
Cái Dijkstra nó là tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh còn lại của đồ thị, như a @nguyenchiemminhvu đã nói thì nó dùng phương pháp Quy hoạch động, dùng 2 mảng C và P có số phần tử bằng số đỉnh của đồ thị, C[i] sẽ lưu lại giá trị của đường đi ngắn nhất từ đỉnh đã chọn đến đỉnh i. P[i] là đỉnh kề trước của đỉnh i trong đường đi ngắn nhất đó. Mặc định với đỉnh được chọn làm đỉnh gốc thì C[i]=0, P[i]=-1, còn những đỉnh có bậc=0 thì C[i]=vô cực, P[i]=-1. Khi đưa ra đường đi từ đỉnh gốc đến đỉnh i thì ta sẽ gọi quay lui từ P[i] về đỉnh gốc, ví dụ P[i]=j, P[j]=k, P[k]=đỉnh gốc, thì đường đi là đỉnh gốc->k->j->i.
Sách của thầy Lê Minh Hoàng Code ko thiếu.
Quan Trọng là hiểu hay Không @drgnz chỉ muốn hiểu hơn thôi
Sách của thầy Hoàng có code + hình vẽ + giải thích khá cặn kẽ nhé
Còn hiểu hay ko thì còn do bạn thôi.
Mình ngu lắm