Kênh Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
Monday, March 10, 2014

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:
graph
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
Untitled
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
Untitled
Hình 3
 - Hình 4: Hàm dijkstra + input: đỉnh bắt đầu và đỉnh kết thúc
outputtổng trọng số và thứ tự đi giữa các đỉnh từ đỉnh bắt đầu đến đỉnh kết thúc.
Untitled
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
Untitled
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…

0 comments:

Post a Comment

Popular Posts