Thuật toán Dijkstra – Tìm đường đi ngắn nhất dựa vào trọng số

Thuật toán Dijkstra – Tìm đường đi ngắn nhất dựa vào trọng số

by lhchuong

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.

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

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…