[Java – Thuật toán] Mô phỏng thuật toán Dijkstra tìm đường đi ngắn nhất
Về thuật toán, bạn có thể xem lại tại bài viết Tìm đường đi ngắn nhất Dijkstra, Floyd. Bài này mình sẽ giới thiệu tới các bạn chương trình mô phỏng thuật toán Dijkstra có đồ họa trên Java, đây cũng là đề tài thực tập cơ sở của mình.
Update ngày 23/05/2015: Sửa lỗi không load được icon trên windows.
Chương trình cho phép người dùng vẽ đồ thị một cách nhanh chóng và dễ dàng, các điểm có thể kéo đi kéo lại, xóa, sửa tri phí (trọng số), … hoặc có thể dùng các đồ thị có sẵn trong phần demo. Và khi chạy sẽ hiển thị quá trình đường đi trên cả đồ thị cũng như phần bên dưới Log. Dưới cùng còn có một bảng để mô tả các công việc mà khi làm bằng tay chúng ta cần làm để tìm đường đi ngắn nhất. Chương trình cũng cho phép lưu lại đồ thị, mở đồ thị đã lưu. Thực ra thì nói nó cũng dài, mình sẽ nói các chức năng của chương trình trong video dài 7 phút dưới đây.
Lưu ý muốn chạy được file *jar bạn cần cài đặt JDK cho máy.
Download Mã nguồn và file jar của chương trình
Mọi thắc mắc, góp ý xin liên hệ trực tiếp với mình qua Email.
Tham khảo: Sản phẩm của tôi
Thank you!
Bạn cho mình hỏi là trong code của chương trình thì đâu là hàm thực hiện thuật toán dijkstra?
Thật xin lỗi là do khi code chưa có kinh nghiệm nên đã không chú thích phù hợp trong code.
Bạn để ý trong Class MyDijkstra có 2 hàm dijkstra và dijkstraStep. Đó là 2 hàm thưc hiện thuật toán và thực hiện thuật toán theo từng bước. 2 hàm tương ứng là tracePath và tracePathStep truy vết đường đi và truy vết đường đi theo từng bước.
cho e hỏi chút là a đang hướng dẫn trên chtrinh j thế ạ?
Chương trình do mình làm đó bạn. Bạn có thể download ở cuối bài viết đó.
đây có phải áp dụng thuật toán tham lam không anh?
Đây là Dijkstra mà
Dijkstra là dựa trên “greedy algorithm” mà bạn. Bản chất là thế, chẳng qua nó áp dụng cho graph thôi. Mình thấy bạn kia hỏi có sai gì đâu. Thuật toán Floyd-Warshall thì dựa vào “dynamic programming” mà.
a ơi. e đang làm về thuật toán dijkstra bằng c++. e đã chạy code nhưng khi chạy phải chèn file ma trận .txt để đọc đường đi. giờ e muốn vẽ đồ thị như của a thì làm tn ạ?
Nếu bạn dùng C thì nên tìm hiểu đồ họa trong nó thì mới làm được.
Bạn có thể tham khảo bài này, hoặc đọc tài liệu ở cuối bài đó về đồ họa trong C
https://www.cachhoc.net/2013/10/03/cc-do-hoa-trong-dev-c/
a ơi. nhưng e làm bằng c++. chạy trên visual cơ. phải làm tn ạ?
Cái này thì mình không rõ rồi. Mình không dùng nó bao giờ cả :3
anh có mô phỏng bằng C# không anh?
Mình không có demo trên C# bạn ah 🙂
anh có thể cho e xin link down jdk được không, e có cài mấy lần mà không mở được bản demo này của anh, em toàn học C# nên gà khoảng java này quá 😀
Ban vao day: http://www.oracle.com/technetwork/java/javase/downloads/index.html
anh ơi, em cài java xong, thì khi mở java, hiện bảng java control panel, e phải làm gì tiếp theo vậy a?
Vậy giờ bạn muốn làm gì? :v
Mình down về nhưng file dijkstra.jar chạy không được, không như minh họa
Bạn xem lại xem đã cài đặt jdk thành công chưa nhá, để cho chắc chắn bạn xem video hướng dẫn sau:
a ơi cho em hỏi làm sao để chạy được file này khi em đả cài jdk và eclipse rồi a.
Sao lại không chạy được ah. Bạn thử xem chương trình có báo lỗi gì không?
nó báo lỗi unable to access jarfile này ah.e mở file dijkstra.jar không được anh. giúp e với. e đang cần làm báo cáo ạ
bạn liên hệ face mình nhé. mình teamview cho.
fb.com/nguyenvanquan7826
anh cho e xin link hoc do hoa java.nhu baj tren a lam voi !
e cam on..
Mình học trong giáo trình của trường với google những gì không biết thôi, ngày trước cũng bookmark 2,3 link đồ họa đơn giản nhưng cài lại máy bị mất rồi. Bạn chịu khó google là được mà 😀
anh ơi tải JDK về rồi, tải chương trình của anh rồi, làm sao để mở chương trình của anh đây, em ko biết cách mở, file của anh em tải về giải nén dược 1 thư mục có tên là Dijkstra với 1 file rar có tên là Dijkstra.rar
anh reply nhanh nhá anh, em đang cần gấp cái này!
Download về giải nén ra bạn sẽ được 1 thư mục và 1 file như thế này. Thư mục đó là mã nguồn, bạn có thể import vào eclipse để xem, sửa, phát triển. File .jar là file có thể chạy. Muốn chạy được bạn cần cài jdk vào. Còn việc chạy hay cài thế nào bạn google nhá 😉
Lưu ý là có thể máy bạn sẽ không hiện đuôi file nhưng nó vẫn là 1 thư mục và 1 file chạy như ảnh nhé.
thế em muốn mở file jar đó bằng cách nào hả anh, nhấn đúp chuột là được à, mà anh đang xài hệ điều hành ubuntu à, của em là windows 7, phải là ubuntu mới mở được hả anh
Win hay ubuntu thì cũng thế mà :3
á..mình tìm được cái này rồi..bạn ơi cho mình xin cái lưu đồ thuật toán với được ko :((
Lưu đồ thuật toán???
Bạn hiểu được nó là khắc vẽ được, cái này mình cũng vẽ cho nữa thì….
mình học tệ lập trình thiệt mà ..vẽ dùm mình đi..năn nỉ đó..:((
bạn ơi…giúp mình đi mà cho mình cái lưu đồ đi 🙁
Bạn xem tại đây nhé
http://vi.wikipedia.org/wiki/Th%E1%BA%A3o_lu%E1%BA%ADn_Th%C3%A0nh_vi%C3%AAn:Ilen.khtn#L.C6.B0u_.C4.91.E1.BB.93_thu.E1.BA.ADt_to.C3.A1n.5B1.5D
Search google ra rất nhiều mà
ôi .cảm ơn ,cảm ơn,,cảm ơn ban nhiều thật nhiều nhé..bác cáo xong mời bạn 1 chầu hoa quả dầm nhé :))
Ôi xong, t biết bạn ở đâu mà đi ăn đây =))
mình có sdt bạn rồi mà..nhất định mời bạn 1 chầu..mà bạn ở đâu nhỉ :))
Mình trên Thái Nguyên 😉
anh cho e hỏi cái file có đuôi dij sao tạo ra nó vậy anh. em tìm hiểu hũm h mà chẳng hiểu
thế thì xa quá ha 🙁
bạn ơi cho mình hỏi thêm với..cái bài này của bạn giới hạn là bao nhiêu node thế nhỉ? ví dụ mình đi từ node 1 đến 5 thì thời gian của nó có nhanh hơn 1 tới 10 ko vậy.nếu được thì trả lời mình sớm với nhá..cảm ơn bạn nhiều,hi
Không giới hạn nhé, với số điển ít thì thời gian không có khoảng cách, nhiều điểm hơn chắc sẽ trễ chút.
bạn có thể cho mình địa chỉ facebook or đại loại gì không cho mình địa chỉ để mình hỏi vài điều chút 😀
Bạn có thể hỏi trực tiếp ở đây mà 🙂
anh ơi, anh có nguồn download phần mềm này không ạ? anh có thể cho em được không ạ! cảm ơn anh trước!
Mã nguồn ở cuối bài viết đó bạn
bạn ơi b có ctrinh chạy bằng c không.cho mình tham khảo với
Bạn xem tại đây nhá https://cachhoc.net/2013/10/13/thuat-toan-tim-duong-di-ngan-nhat-dijkstra-floyd/
Cho mình xin mã nguồn được không ạ, down theo link trên chỉ có phần file thực thi 😀
Mã nguồn ở bên dưới nhé bạn.
Chào bạn mình được biết bài viết của bạn ở trang https://www.cachhoc.net/2014/06/14/java-thuat-toan-mo-phong-thuat-toan-dijkstra-tim-duong-di-ngan-nhat/
bạn có thể giúp mình vấn đề này được không. khi mình đổi tên gói trong soude code của bạn nguyenvanquan7826 thành AI thì không thể đọc được file demo(thông báo là erro read demo file). bạn có thể giúp mình được không. mình vào file demo.dat đổi nguyenvanquan7826 -> AI rồi mà vẫn không được. Mong bạn giúp đỡ,chân thành cảm ơn bạn . bạn có thể gửi email về nguyenhaidang200291@gmail.com chỉ cách khắc phục cho mình được không
Đã trả lời bạn trong mail nhé.
cho bạn nào cần mà không mở file jar được, các bạn vô Properties – Permissions. Tích vào “Allow executing file as program” là chạy vô tư ^^
Cảm ơn bạn.
Nếu em muốn thêm 1 nút Prev – lùi lại 1 bước + 1 nút Tự động thực hiện theo speed tùy chỉnh thì phải viết sự kiện như thế nào vậy anh ? Một newbie Java thắc mắc ^^!
Cái này bạn xem trong code sẽ thấy có hàm thực hiện bước thứ k. Bạn click pre next thì tăng giảm k là đk.
Vậy còn muốn chương trình chạy tự động theo thanh speed và có thể Pause lại thì phải làm sao anh?
Bạn cũng dựa vào chế độ đó.
Anh có thể demo mẫu để em dễ hình dung hơn được không? em còn gà mờ quá -_- Tks anh trước ^^
Mình chỉ gợi ý bạn đuoẹc thế thôi chứ giờ mình ko nhớ hết đk code trong đó để xem và làm lại. Mấy năm rồi mà…
Vậy em có cần tạo method runPrev(), drawPrev(),… tương tự như runStep() không?
Tùy bạn. Bạn lập trình thì thấy cần thiết hay ko do bạn.
Nếu em muốn từ project này phát triển thêm Tìm cây khung nhỏ nhất thì anh có thể gợi ý cách làm cho em được không ?
Cây khung nhỏ nhất mình cũng chưa làm bao giờ nên ko hứa với bạn được
Đã làm được Prev, cảm ơn anh đã gợi ý ^^ . Mà quá trình chạy sẽ là bấm Next liên tục thì làm thế nào để nút Play nó tự Next mà mình không cần bấm Next vậy? Em thấy 1 vài ví dụ sử dụng Thead với sleep để điều chỉnh tốc độ nhưng trong code của anh lại không sử dụng Thread @@!
Em viết được giải thuật cho cây khung nhỏ nhất = Kruskal rồi thì làm thế nào áp dụng myDraw của anh để vẽ lên đồ thị được vậy ?
public class MyMSTKruskal {
private ArrayList arrLineA = new ArrayList();
private ArrayList arrLineE = new ArrayList();
private ArrayList arrMyPoint = new ArrayList();
int p[];
int sodinh, chiso=0;
int TongTS =0;
int socanh;
private boolean mapType = false;
public void input()
{
sodinh = arrMyPoint.size()-1;
socanh = arrLineE.size()-1;
for(int i=0;i<socanh;i++)
arrLineA.add(null);
p = new int[sodinh+1];
System.out.println("so dinh : "+sodinh);
for(int i =0;i<sodinh;i++)
{
p[i] = i;
}
System.out.println("so canh : "+socanh);
for(int i=0;i<socanh;i++)
{
System.out.println("nhap u : "+arrLineE.get(i+1).getIndexPointA());
System.out.println("nhap v : "+arrLineE.get(i+1).getIndexPointB());
System.out.println("nhap trong so : "+arrLineE.get(i+1).getCost());
}
}
public void sort()
{
Collections.sort(arrLineE, new MyLineComparator());
// for(MyLine emp : arrLineE){
// System.out.println(emp);
// }
}
public void kruskal()
{
sort();
for (int i = 0; i < socanh; i++)
if(p[arrLineE.get(i+1).getIndexPointA()]!=p[arrLineE.get(i+1).getIndexPointB()])
{
arrLineA.set(chiso++, arrLineE.get(i+1));
System.out.println(arrLineA.get(i));
int t=max(p[arrLineE.get(i+1).getIndexPointA()],p[arrLineE.get(i+1).getIndexPointB()]);
int k=min(p[arrLineE.get(i+1).getIndexPointA()],p[arrLineE.get(i+1).getIndexPointB()]);
p[arrLineE.get(i+1).getIndexPointA()]=p[arrLineE.get(i+1).getIndexPointB()]=k;
for(int j=0;j<sodinh;j++)
if(p[j]==t)
p[j]=k;
}
}
public void output()
{
System.out.println("cac canh can chon : ");
for(int i=0;ib) return a;
else return b;
}
public int min(int a, int b)
{
if(a<b) return a;
else return b;
}
Cái này là tư duy và từng bước thuật. Bạn phải tự nghĩ thôi.
anh có làm về giải thuật A* ko cho em xin với ạ
a ơi phần khởi tạo khi hiển thị kết quả giống các bước trong giáo trình sao tất cả lại là vô cùng ạ? cảm ơn a!
Anh ơi, a có source code tìm đường đi chu trình euler k cho e ới
Anh không có 🙂
Anh ơi cho e hỏi đây có phải là đề tài đồ án giải thuật và lập trình không ạ , và đồ án là mình phải làm một chương trình có giao diện sử dụng như phần mềm của a vậy hả ? 🙂 , e chưa hiểu về đồ án cho lắm
Có thể coi là vậy, nhưng tùy cái mà có cần chương trình không. 🙂
A ơi Em đang làm về thuật toán này mà dùng matlab. A hỗ trợ em được k ạ
Matlab mình ko rõ nên không giúp được bạn rồi. Bạn cố gắng dựa vào tư tưởng để chuyển về code matlab nhé.
còn cái phần mềm trên là anh tự viết hay sao ạ
ukm 🙂
Anh ơi theo bài anh thì khi vẽ các đỉnh các đỉnh sẽ được gán theo thứ tự 1-2-3,.. nhưng bây giờ em muốn thay đổi các đỉnh theo thứ tự là A-B-C,…. v có được hk. Nếu được thì làm như nào v ạ.
Anh ơi em xem thuật toán, các biến, các hàm trong class MyDijkstra mà hk hiểu. Anh có thể giải thích cho em từng hàm cũng như dòng lệnh được hk ạ. Em đang rất cần. Nếu có đkien gì a mail cho e ạ
Mở làm sao để xem code ạ
Bạn download về giải nén ra nhé.
anh ơi em tải về chạy bị lỗi
Error chose points or don’t Update graph to choé points
Bạn chưa chọn điểm đầu hoặc điểm cuối, Hoặc chưa click nút đồng bộ để sinh ra đồ thị sau khi vẽ hoặc chọn demo.
bạn ơi sao mình tải về ko có file jar vậy
Bạn giải nén ra sẽ thấy nhé.
anh ơi….Hạn chế và hướng phát triển của thuật toán dijkstra là gì vậy a
Bạn hiểu nó và tự tìm hiểu thêm.
cho em hỏi là cái đồ thị trọng số mình làm sao đưa vô được cái giao diện chạy lên vậy