Chương trình mô phỏng thuật toán dijkstra bằng java năm 2024
|
Thuật toán Dijkstra là một trong những thuật toán cổ điển để giải quyết bài toán tìm đường đi ngắn nhất từ một điểm cho trước tới tất cả các điểm còn lại trong đồ thị có trọng số. Trong bài viết này chúng ta cùng tìm hiểu ý tưởng cơ bản của thuật toán Dijkstra. Mục lục1. Ý tưởngThuật toán Dijkstra có thể giải quyết bài toán tìm đường đi ngắn nhất trên đồ thị vô hướng lẫn có hướng miễn là trọng số không âm. Ý tưởng cơ bản của thuật toán như sau:
2. Ví dụĐể dễ dàng hiểu ý tưởng của thuật toán. Chúng ta cùng xem ví dụ với đồ thị vô hướng $G$. Thuật toán Dijkstra sẽ tìm khoảng cách từ đỉnh gốc $0$ tới tất cả các đỉnh còn lại trong đồ thị $G$. Đồ thị $G$ Đầu tiên, khởi tạo khoảng cách nhỏ nhất ban đầu tới các đỉnh khác là $+\infty$ và khoảng cách tới đỉnh gốc là 0. Ta được danh sách các khoảng cách tới các đỉnh.
Chọn đỉnh 0 có giá trị nhỏ nhất, xét các đỉnh kề của đỉnh 0: Xét đỉnh 1, khoảng cách từ gốc đến đỉnh 1 là 2.5 < $\infty$ nên ghi nhận giá trị mới là $(2.5, 0)$ (nghĩa là khoảng cách đến đỉnh gốc hiện tại ghi nhận là 2.5, đỉnh kề liền trước là đỉnh 0). Xét tương tự cho đỉnh 2 và 3, ta được dòng thứ 2 trong bảng.
Sau khi xét tất cả các đỉnh ta chọn đỉnh 2 có khoảng cách nhỏ nhất và ghi nhận để xét tiếp. Tiếp tục xét đỉnh kề của 2 là đỉnh 4 và 5 với nguyên tắc nêu ở trên. Xét đỉnh 4, khoảng cách từ đỉnh gốc đến đỉnh 4 sẽ bằng khoảng cách từ đỉnh gốc tới đỉnh 2 cộng khoảng cách từ 2 đến 4. Nghĩa là $2.0+0.6=2.6$ nên ta ghi nhận khoảng cách tại đỉnh 4 là $(2.6, 2)$. Xét tương tự cho đỉnh 5.
Lúc này ta chọn được đỉnh 3 có khoảng cách nhỏ nhất, xét đỉnh kề của đỉnh 3 là đỉnh 5. Khoảng cách từ gốc tới đỉnh 5 $=2.1+2.5=4.6$ lớn hơn khoảng cách hiện tại được ghi nhận, vì vậy giá trị tại đỉnh 5 không đổi.
Đỉnh 1 là đỉnh được chọn tiếp theo, xét đỉnh kề của 1 là đỉnh 4. Khoảng cách từ đỉnh gốc không nhỏ hơn khoảng cách hiện tại nên ta không cập nhật gì ở đỉnh này. Hỗ trợ thanh toán qua INTERNET BANKING tất cả các ngân hàng: VietcomBank, BIDV, VietinBank, SacomBank, TechcomBank, Á Châu, TPbank, MBbank, AgriBank, VPbank, SHB, MaritimeBank, DongAbank, VIB, EximBank, HDbank, NCB, Việt Á, OceanBank, PGbank, BacAbank... Bạn cần đăng nhập để tải code qua chức năng này! ĐĂNG NHẬP NGAY Hỗ trợ CHUYỂN KHOẢN TRỰC TIẾP qua các số tài khoản ngân hàng: VietcomBank, BIDV, VietinBank, SacomBank, TechcomBank, Á Châu, TPbank, MBbank, AgriBank, VPbank, SHB, MaritimeBank Bạn cần đăng nhập để tải code qua chức năng này! ĐĂNG NHẬP NGAY Chương trình là giải pháp trực quan của việc ứng dụng thuật toán Dijkstra và Floyd. Bạn có thể dùng trong nghiên cứu và biện giải dễ hiểu về thuật toán hoặc ứng dụng giải quyết các bài toán thực tiễn- Bạn nhập vào tùy ý số đỉnh của đồ thị bằng cách click chuột phải vào vị trí đặt đỉnh - Vẽ các cạnh bất kỳ giữa các đỉnh và có thể điều chỉnh trọng số, có hướng hoặc vô hướng - Bạn có thể di dời các vị trí cho dễ quan sát - Lựa chọn cặp đỉnh và đỉnh xuất phát bất kỳ - Mô phỏng bằng Dijkstra hoặc Floyd trực quan sinh động Nguồn: Sharecode.vn |
