Ở đây, mình có viết một chương trình tìm đường đi ngắn nhất bằng C#, dữ liệu test với đồ thị có 6 đỉnh và dữ liệu thật của một nút giao thông có 5011 đỉnh.

Trong đó, khi mình test với dữ liệu thật của một nút giao thông có 5011 đỉnh thì thời gian thực hiện ở mức chấp nhận được khi chỉ mất 36 mili giây để tìm được đường đi ngắn nhất.

Trong bài học trước, chúng ta đã cùng nhau đi tìm hiểu về thuật toán Floyd-Warshall trong tìm kiếm đường đi ngắn nhất trên đồ thị. Hôm nay, chúng ta sẽ cùng nhau đi tìm hiểu về một thuật toán có thể coi là thuật toán phổ biến nhất trong tìm kiếm đường đi ngắn nhất. Để biết cụ thể, hãy cùng nhau bắt đầu bài học nào!

Nội dung

Để có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:

• Các kiến thức cần thiết để theo dõikhóa học
• Đồ thị và cây
• BFS và DFS
• Priority Queue
• Thuật toán Floyd-Warshall

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:

• Thuật toán Dijkstra

Thuật toán Dijkstra

Bài toán đặt ra

Ta có một bài toán như sau:

Cho một đồ thị có hướng gồm đỉnh [đánh số từ 1 đến], cạnh có hướng và có trọng số là số nguyên không âm. Cho một đỉnh, hãy tìm độ dài đường đi ngắn nhất từ đỉnh đến tất cả các đỉnh còn lại. Nếu như không tồn tại đường đi giữa hai đỉnh, in ra -1.

Input:

Output:

Ví dụ:

Input Output

7 8 1

1 2 4

1 3 5

1 4 2

4 2 1

4 6 4

3 5 3

6 5 1

1 5 8

0

3

5

2

7

6

-1

Giải thích ví dụ:

Đây là đồ thị minh hoạ cho ví dụ trên

_howkteam_vn.png]

Ý tưởng

Ý tưởng của Dijkstra về cơ bản khá giống với thuật toán Floyd. Với một cạnh nối liền hai đỉnh và, ta sẽ so sánh độ dài đường đi trước đây với đường.

Tại mỗi bước, ta sẽ chọn ra một đỉnh mà ta biết chắc chắn đường đi từ là đường đi ngắn nhất. Sau đó, ta sẽ xét tất cả các đỉnh mà có cạnh liên kết trực tiếp rồi tối ưu đường đi dựa trên đường đi.

Cách cài đặt

Trước hết, để thể hiện một cạnh, ta sẽ sử dụng các vector với kiểu dữ liệupair. pair là một cấu trúc cho phép ta lưu trữ hai phần tử. Ta có thể truy cập vào 2 phần tử củapair thông qua hai phương thức first và second.

Ví dụ:

`

include

using namespace std; int main[]{

pair myPair[2];  
// Có 2 cách khởi tạo pair  
myPair[0] = make_pair[1, 2];  
myPair[1] = {2, 3};
cout > s;  
for[int i = 0 ; i < m ; ++i]{  
    int u, v, w;  
    cin >> u >> v >> w;  
    adj[u].push_back[{v, w}];  
}  
Dijkstra[s];  
for[int i = 1 ; i  m >> s;  
for[int i = 0 ; i < m ; ++i]{  
    int u, v, w;  
    cin >> u >> v >> w;  
    adj[u].push_back[{v, w}];  
}  
Dijkstra[s];  
for[int i = 1 ; i