Thuật toán Dijkstra – Tìm đường đi ngắn nhất dựa vào trọng số
1. Mô tả:
- Đồ thị sẽ được tổ chức như Hình 1:
Hình 1
- Chúng ta sẽ thực hiện việc tìm đường đi ngắn nhất dựa vào trọng số từ đỉnh 1 -> đỉnh 10.
2. Cài đặt:
Chúng ta sẽ tiến hành cài đặt bằng ngôn ngữ C++
- Hình 2: tiến hành lưu đồ thị trên theo ma trận kề, với 10 đỉnh
Hình 2
- Hình 3: Gọi hàm trong main, ở đây 0 là đỉnh bắt đầu và 9 là đỉnh kết thúc
Hình 3
- Hình 4: Hàm dijkstra + input: đỉnh bắt đầu và đỉnh kết thúc
+ output: tổng trọng số và thứ tự đi giữa các đỉnh từ đỉnh bắt đầu đến đỉnh kết thúc.
+ output: tổng trọng số và thứ tự đi giữa các đỉnh từ đỉnh bắt đầu đến đỉnh kết thúc.
Hình 4
- Hình 5: Hàm printPath
+ input: đỉnh bắt đầu và đỉnh kết thúc, mảng lưu thứ tự các đỉnh
+ ouput: in đường đi đã được thiết lập từ đỉnh bắt đầu và đỉnh kết thúc
+ input: đỉnh bắt đầu và đỉnh kết thúc, mảng lưu thứ tự các đỉnh
+ ouput: in đường đi đã được thiết lập từ đỉnh bắt đầu và đỉnh kết thúc
Hàm 5
Như vậy là tôi vừa hoàn thành việc mô tả và cài đặt thuật toán Dijkstra, trong bài viết tôi không giải thích chi tiết các bước vì đã có rất nhiều trong các diễn đàn lớn…
Cách sử dụng chức năng maps này để tìm đường đi nằm mơ thấy rắn nước cắnđó là người dùng truy cập vào địa chỉ maps.vinalo.com gà bị rắn cắn có ăn được không và chỉ cần nhập địa điểm cần tìm … website sẻ tính toán cà pháo có độc không và đưa ra địa chỉ của của địa điểm này trên phèn chua có phải là đường phèn không bản đồ và những con đường dẩn bạn đến địa điểm bạn tìm đó, hiện này thì maps của vinalo đã có app ứng dụng trên điện thoai di động rất tiện lợi để mọi người có thể tim duong khí argon có độc không hay tìm địa điểm bất cứ khi nào đang đi trên đường chỉ cần có lá dứa có độc không chiếc smart phone có kết nối internet.
ReplyDelete