Thuật toán Dijsktra: C++, Python Ví dụ về mã
Sarah Chen
Con đường ngắn nhất hoặc khoảng cách ngắn nhất là gì?
Đường đi từ đỉnh nguồn tới đỉnh đích có chi phí nhỏ nhất là đường đi ngắn nhất hoặc khoảng cách ngắn nhất. Trong lý thuyết đồ thị, có thể có nhiều tuyến đường từ một nguồn đến đích. Giữa các tuyến đường này, nếu có một tuyến đường có chi phí tối thiểu thì chúng ta có thể gọi đó là thuật toán đường đi ngắn nhất.
Ở đây “Chi phí” có nghĩa là số lượng nút trong tuyến hoặc tổng chi phí trên mỗi tuyến. Một đường dẫn có thể có một hoặc nhiều cạnh. Sự kết nối giữa hai đỉnh được gọi là “cạnh”. Có nhiều loại thuật toán đường đi ngắn nhất khác nhau, như Thuật toán Dijkstra, thuật toán Bellman-Ford, v.v.
Ở đây chúng ta thảo luận về Thuật toán Dijkstra
Chúng ta hãy xem biểu đồ có trọng số sau:
- Thuật ngữ “Có trọng số” có nghĩa là di chuyển chi phí từ nút này sang nút khác. Ví dụ: chuyển từ nút 1 sang nút 2, chi phí hoặc trọng lượng là 1.
- Đường dẫn giữa nút 1 đến nút 2 được gọi là cạnh.
- “Không được định hướng” có nghĩa là bạn có thể di chuyển nút này sang nút khác và quay lại nút trước đó. Vì vậy, nếu chúng ta cố gắng tìm tất cả các tuyến đường từ nút 1 đến nút 7 thì nó sẽ là:
| Tuyến đường hoặc Đường dẫn | Phí Tổn |
|---|---|
| 1-2-6-7 | (1+3+3) = 7 |
| 1-2-3-7 | (1+9+1) = 11 |
| 1-3-7 | (7+1) = 8 |
| 1-4-5-7 | (6+2+5) = 13 |
Trong số bốn tuyến đường này, chúng ta có thể thấy rằng tuyến đường đầu tiên sẽ tiêu tốn của chúng ta 7. Vì vậy, đây là con đường ngắn nhất về mặt chi phí.
Thuật toán Dijkstra hoạt động như thế nào
Thuật toán Dijkstra có thể tìm khoảng cách ngắn nhất trong cả đồ thị có trọng số có hướng và vô hướng. Thuật toán này mang tính tham lam vì nó luôn chọn nút ngắn nhất hoặc gần nút gốc nhất. Thuật ngữ “tham lam” có nghĩa là trong số một tập hợp các kết quả hoặc kết quả, Thuật toán sẽ chọn kết quả tốt nhất trong số đó.
Ở đây, chúng tôi đang cố gắng tìm những con đường ngắn nhất trong số tất cả các tuyến đường khác. Vì vậy, Thuật toán Dijkstra tìm thấy tất cả các đường đi ngắn nhất từ một nút đích duy nhất. Kết quả là, nó hoạt động giống như một thuật toán tham lam.
Trong phần “ví dụ” bên dưới, bạn sẽ thấy cách tiếp cận từng bước. Nó hoạt động như sau:
Bước 1) Khởi tạo nút bắt đầu với chi phí 0 và phần còn lại của nút là Chi phí vô cực.
Bước 2) Duy trì một mảng hoặc danh sách để theo dõi các nút đã truy cập
Bước 3) Cập nhật chi phí nút với chi phí tối thiểu. Nó có thể được thực hiện bằng cách so sánh chi phí hiện tại với chi phí đường đi. (Trình diễn được hiển thị trong phần ví dụ)
Bước 4) Tiếp tục bước 3 cho đến khi tất cả các nút được truy cập.
Sau khi hoàn thành tất cả các bước này, chúng ta sẽ tìm ra đường đi có chi phí tối thiểu từ nguồn đến đích.
Sự khác biệt giữa Dijkstra và BFS, DFS
Sự khác biệt chính giữa Dijkstra và BFS-DFS là Dijkstra là thuật toán tìm đường ngắn nhất và BFS, DFS là thuật toán tìm đường. Trong trường hợp chung, BFS và DFS không xem xét chi phí khi tìm đường dẫn. Vì vậy, các thuật toán này không thể đảm bảo đường đi ngắn nhất.
Trình diễn lưới 2D về cách hoạt động của BFS
Phần trình diễn này chỉ ra rằng BFS chỉ tìm thấy đường dẫn. Tuy nhiên, nó không quan tâm đến trọng lượng của đường đi. BFS (Tìm kiếm theo chiều rộng đầu tiên) giả định rằng việc di chuyển từ nút này sang nút khác sẽ chỉ tốn 1.
Nhưng chúng ta hãy xem một biểu đồ ví dụ:
Ở đây, nó tìm thấy một đường dẫn ở cấp độ 2. BFS đi qua Đồ thị theo thứ tự cấp độ. Vì vậy, nó di chuyển như sau:
Bước 1) Bắt đầu từ nút “1” và truy cập tất cả các nút lân cận 2,3,4
Bước 2) Đánh dấu nút 2,3,4 là cấp 1 và truy cập các nút lân cận của chúng. Nó sẽ tiếp tục khám phá tất cả các nút lân cận cho đến khi đến được nút đích.
Về mặt DFS, nó sẽ đi qua đường dẫn từ 1 đến 7 như sau:
- 1→2→3→7 (Chi phí gốc 10, Chi phí DFS 3)
- 1→2→6→7 (Chi phí gốc 7, Chi phí DFS 3)
- 1→3→7 (Chi phí ban đầu 8, Chi phí DFS 2)
- 1→4→5→7 (Chi phí gốc 13, Chi phí DFS 3)
Như chúng ta thấy, DFS tính toán chi phí đường đi của nó bằng số độ sâu hoặc số cạnh.
DFS thực hiện những điều sau:
- DFS có thể tìm đường dẫn từ nguồn (đỉnh bắt đầu) đến đích.
- Nó không thể đảm bảo liệu đường dẫn được phát hiện từ nút nguồn đến đích có phải là đường dẫn ngắn nhất hay không.
Tuy nhiên, xét về mặt Thuật toán Dijkstra, nó sẽ chọn các cạnh dựa trên chi phí của chúng. Là một thuật toán tham lam, nó sẽ chọn các đường dẫn có chi phí tối thiểu hoặc tốt nhất.
Ví dụ về thuật toán Dijkstra
Thuật toán Dijkstra sử dụng chi phí hoặc trọng số để tính tổng chi phí của đường đi.
Mục tiêu của Thuật toán Dijkstra là giảm thiểu tổng chi phí hoặc trọng lượng này. Trong ví dụ hiển thị ở trên, chúng tôi tìm đường đi tốt nhất từ nút 1 đến nút 7, sau đó tính toán tất cả chi phí.
Trong Thuật toán Dijkstra, nó sẽ tìm đường đi ngắn nhất bằng cách tính trọng số. Nó sẽ không tìm kiếm tất cả các đường dẫn có thể. Chúng ta hãy chứng minh Thuật toán Dijkstra bằng một ví dụ. Ví dụ: bạn được yêu cầu tìm đường đi ngắn nhất từ nút 1 đến nút 7.
Đối với quá trình này, các bước được đưa ra dưới đây:
Bước 1) Khởi tạo chi phí nút bắt đầu thành 0.
Phần còn lại của nút, gán “Thông tin”. Điều đó có nghĩa là không có đường dẫn nào tồn tại giữa đỉnh bắt đầu (nguồn) và nút hoặc đường dẫn chưa được truy cập.
Bước 2) Khi bạn chọn nút 1, nó sẽ được đánh dấu là đã truy cập. Sau đó cập nhật tất cả các nút lân cận của nút 1. 2,3,4 là các nút lân cận của nút 1.
Trong khi cập nhật chi phí, chúng ta cần thực hiện theo quy trình dưới đây:
Chúng tôi có thể cập nhật chi phí của từng nút bằng công thức trên. Ví dụ: chúng tôi đang ở nút 1 và chúng tôi cần cập nhật chi phí của nút liền kề 2,3,4.
Sau khi cập nhật giá thành hoặc trọng lượng sẽ như sau:
Bước 3) Đối với nút “2”, hàng xóm là 6 và 3. Chúng tôi đang cập nhật chi phí ở mức “6” bằng cách so sánh vô cực (giá trị hiện tại). Chi phí của nút 2 + chi phí đường dẫn từ 2 đến 6. Nói một cách đơn giản, nút “6” sẽ có chi phí là 1+3 hoặc 4.
Nút 3 là hàng xóm của nút 2. Tuy nhiên, chúng tôi đã tính chi phí của nó ở bước trước là 7. Bây giờ, nếu đường dẫn của chúng tôi là 1-2-3, nút 3 sẽ có chi phí là 10. Đường dẫn 1-2- 3 sẽ có giá 10, trong khi 1 đến 3 sẽ có giá 7.
Bước 4) Đối với nút 3, nút lân cận là 7. Vì vậy, so sánh giá trị hiện tại của nút 7 với chi phí đường đi (7+1) hoặc 8, chúng tôi sẽ cập nhật chi phí của nút 7. Đó là 8.
Vì vậy, chúng ta tìm đường đi từ nút 1 đến nút 7 và nó là 1→ 3→ 7. Chi phí là 8.
Bước 5) Đối với nút 4, chúng tôi sẽ cập nhật chi phí nút liền kề của nó cho phù hợp. Vì vậy, nút “5” sẽ có chi phí cập nhật là 8. Sau bước 4,5, nó sẽ trông như thế này:
Bây giờ, đường 1-3-7 có chi phí là 8 (trước đây). Nút “7” không được đánh dấu là đã truy cập vì chúng tôi có thể tiếp cận nút “7” từ nút “6”. Đường đi “1-2-6” có chi phí là 4. Vì vậy, đường dẫn 1-2-6-7 sẽ có chi phí là 7.
Vì 7 < 8, đó là lý do tại sao đường đi ngắn nhất từ đỉnh nguồn “1” đến đỉnh đích “7” sẽ là 1-2-6-7 và chi phí là 7. Trước đây là 1-3-7 và chi phí là 8.
Vì vậy, Biểu đồ cuối cùng sẽ trông như thế này:
Cạnh được đánh dấu bằng một đường màu đen là đường đi ngắn nhất của chúng ta từ 1 đến 7 và chúng ta sẽ phải trả 7.
Thuật toán giả mã Dijkstra
Đây là mã giả cho Thuật toán Dijkstra
Dijkstra(G, S):
for each vertex V in G
distance[V] & lt; - Infinity
previous[V] & lt; - NULL
if V does not equal S, then,
(priority queue) Q.push(V)
distance[S] = 0
While Q is not empty
U & lt; - Extract the MIN from Q
For each unvisited adjacent V of U
TotalDistance & lt; - distance[U] + edge_cost(U, V)
if TotalDistance is less than distance[V], then
distance[V] & lt; - TotalDistance
previous[V] & lt; - u
return distance, previous
C++ triển khai thuật toán Dijkstra
Để thực hiện thuật toán Dijkstra bằng cách sử dụng C++, đây là mã:
#include <bits/stdc++.h>
using namespace std;
#define size 7
int minimumDistance(int distance[], bool visited[]) {
int min = INT_MAX;
int min_index = INT_MAX;
for (int i = 0; i < size; i++) {
if (!visited[i] & amp; & distance[i] <= min) {
min = distance[i];
min_index = i;
}
}
return min_index;
}
void printParentPath(int parent[], int i) {
if (parent[i] == -1) {
return;
}
printParentPath(parent, parent[i]);
cout << i + 1 << " ";
}
void dijkstra(int graph[size][size], int source) {
int distance[size];
bool visited[size];
int parent[size];
for (int i = 0; i < size; i++) {
parent[0] = -1;
distance[i] = INT_MAX;
visited[i] = false;
}
distance[source] = 0;
for (int i = 0; i < size - 1; i++) {
int U = minimumDistance(distance, visited);
visited[U] = true;
for (int j = 0; j < size; j++) {
int curr_distance = distance[U] + graph[U][j];
if (!visited[j] & amp; & graph[U][j] & amp; &
curr_distance < distance[j]) {
parent[j] = U;
distance[j] = curr_distance;
}
}
}
cout << "Vertex\t\tDistance\tPath" << endl;
for (int i = 1; i < size; i++) {
cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t"
<< source + 1 << " ";
printParentPath(parent, i);
cout << endl;
}
}
int main() {
int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0},
{7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0},
{0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3},
{0, 0, 0, 0, 5, 3, 0}};
dijkstra(graph, 0);
}
Đầu ra:
Vertex Distance Path 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
Python triển khai thuật toán Dijkstra
Để thực hiện thuật toán Dijkstra bằng cách sử dụng mãng xà, đây là mã:
num_of_vertex = 7
def minimumDistance(distance, visited):
_min = 1e11
min_index = 1e11
for i in range(num_of_vertex):
if not visited[i] and distance[i] & lt; = _min:
_min = distance[i]
min_index = i
return min_index
def printParentNode(parent, i):
if parent[i] == -1:
return
printParentNode(parent, parent[i])
print("{} ".format(i + 1), end = "")
def dijkstra(graph, src):
distance = list()
visited = list()
parent = list()
for i in range(num_of_vertex):
parent.append(-1)
distance.append(1e11)
visited.append(False)
distance[src] = 0
for i in range(num_of_vertex - 1):
U = minimumDistance(distance, visited)
visited[U] = True
for j in range(num_of_vertex):
curr_distance = distance[U] + graph[U][j]
if not visited[j] and graph[U][j] and curr_distance & lt;
distance[j]: parent[j] = U
distance[j] = curr_distance
print("Vertex\t\tDistance\tPath")
for i in range(num_of_vertex):
print("{}->{}\t\t{}\t\t{}
".format(src + 1, i + 1, distance[i], src + 1), end = "")
printParentNode(parent, i)
print("")
graph = [
[0, 1, 7, 6, 0, 0, 0],
[1, 0, 9, 0, 0, 3, 0],
[7, 9, 0, 0, 0, 0, 1],
[6, 0, 0, 0, 2, 0, 0],
[0, 0, 0, 2, 0, 0, 0],
[0, 3, 0, 0, 0, 0, 3],
[0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)
Đầu ra:
Vertex Distance Path 1->1 0 1 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
Chúng ta có thể thấy rằng Thuật toán tính toán khoảng cách ngắn nhất từ nút nguồn.
Ứng dụng thuật toán Dijkstra
Thuật toán Dijkstra có rất nhiều cách sử dụng. Trong số đó, nó được sử dụng rộng rãi trong lĩnh vực mạng. Dưới đây là một số cách sử dụng Thuật toán Dijkstra trong đời thực:
Dijkstra trên bản đồ Google: Về cơ bản, Thuật toán này là xương sống để tìm đường đi ngắn nhất. Như chúng ta có thể thấy từ đầu ra đoạn mã trên.
Google không sử dụng thuật toán Dijkstra đơn giản. Thay vào đó, nó sử dụng một phiên bản sửa đổi. Khi bạn chọn một điểm đến, nó sẽ hiển thị cho bạn nhiều đường đi trong Google Map. Trong số các đường dẫn này, một số đường dẫn được sắp xếp cho người dùng. Những con đường được chọn này dựa trên “thời gian”. Vì vậy, “thời gian” là chi phí biên cho đường đi ngắn nhất.
Dijkstra trong định tuyến IP: Định tuyến IP là một thuật ngữ mạng. Nó có nghĩa là gói dữ liệu của bạn được gửi đến người nhận thông qua các đường dẫn khác nhau như thế nào. Những đường dẫn này bao gồm các bộ định tuyến, máy chủ, v.v. Trong định tuyến IP, có nhiều loại giao thức khác nhau.
Các giao thức này giúp bộ định tuyến tìm đường đi ngắn nhất để gửi dữ liệu. Một trong những tên giao thức là “OSPF (Open Shortest Path First)”. OSPF sử dụng thuật toán dijkstra. Bộ định tuyến duy trì một bảng các tuyến đường. Mỗi bộ định tuyến chia sẻ bảng của mình với các bộ định tuyến lân cận. Sau khi nhận được bảng đã cập nhật, chúng phải tính toán lại tất cả các đường dẫn. Vào thời điểm đó, bộ định tuyến sử dụng Thuật toán Dijkstra.
Hạn chế của thuật toán Dijkstra
Thuật toán Dijkstra không thể đảm bảo đường đi ngắn nhất trong biểu đồ cạnh âm. Thuật toán Dijkstra tuân theo các phương pháp sau:
- Một đường đi ngắn nhất sẽ được đi từ nút này sang nút khác.
- Khi đường đi ngắn nhất giữa hai nút được chọn, nó sẽ không được tính lại.
Ở đây, hãy chú ý hai ví dụ có cạnh âm.
Trong biểu đồ bên trái, có ba đỉnh. Dijkstra sẽ chạy trên Graph như sau:
Bước 1) Đỉnh bắt đầu “1” sẽ được khởi tạo bằng XNUMX. Các nút khác sẽ có vô cùng.
Bước 2) Đánh dấu Nút “1” là đã truy cập và đưa nó vào đường đi ngắn nhất.
Bước 3) Khoảng cách từ nút nguồn 1 đến các nút “2” và “3” được đặt thành vô cùng, vì đường đi ngắn nhất vẫn chưa được tính toán. Vì vậy, bất kỳ đường đi nào có chi phí nhỏ hơn vô cực sẽ được thêm vào đường đi ngắn nhất (cách tiếp cận tham lam).
Bước 4) Cập nhật khoảng cách từ đỉnh nguồn hoặc nút nguồn “1” lên “2”. Trọng lượng hiện tại sẽ là 5 (5
Bước 5) Bây giờ nếu chúng ta kiểm tra khoảng cách ngắn nhất từ nút “1”, chúng ta thấy rằng 5 là khoảng cách ngắn nhất cho cạnh 1–> 2. Vì vậy, nút “2” sẽ được đánh dấu là đã truy cập.
Tương tự, nút “3” cũng sẽ được đánh dấu là đã truy cập vì khoảng cách ngắn nhất là 3.
Tuy nhiên, nếu chúng ta quan sát, có một đường đi 1-3-2 sẽ chỉ tốn 2. Nhưng Dijkstra cho thấy rằng từ nút “1” đến nút “2”, khoảng cách ngắn nhất là 5. Vì vậy, Dijkstra đã không tính được đường đi ngắn nhất khoảng cách một cách chính xác. Lý do nó xảy ra là vì Dijkstra là một thuật toán tham lam. Vì vậy, khi một nút được đánh dấu đã truy cập, nút đó sẽ không được xem xét lại, mặc dù có thể có đường dẫn ngắn hơn. Sự cố này chỉ xảy ra khi các cạnh có chi phí âm hoặc cạnh trọng số âm
Dijkstra không tính được đường đi ngắn nhất giữa hai nút trong trường hợp này. Kết quả là, Thuật toán này có một số nhược điểm. Để giải quyết vấn đề cạnh âm này, một thuật toán khác gọi là “Thuật toán Bellman-Ford” được sử dụng. Thuật toán đó có thể hoạt động với các cạnh âm.
Độ phức tạp của thuật toán Dijkstra
Việc triển khai ở trên sử dụng hai vòng lặp “for”. Các vòng lặp này chạy cho số đỉnh. Vì vậy, độ phức tạp về thời gian là O(V2). Ở đây, thuật ngữ “0” có nghĩa là ký hiệu đưa ra một giả định cho thuật toán Dijkstra.
Chúng ta có thể lưu trữ Biểu đồ bằng cách sử dụng “Hàng đợi ưu tiên”. Hàng đợi ưu tiên là cấu trúc dữ liệu heap nhị phân. Nó sẽ hiệu quả hơn ma trận 2D. Một cạnh có chi phí tối thiểu sẽ có mức độ ưu tiên cao.
Sau đó độ phức tạp thời gian sẽ là O(E log(V)). Ở đây, E là số cạnh và V là số đỉnh.
Độ phức tạp của không gian là O(V2), vì chúng tôi đang sử dụng ma trận kề (mảng 2D). Độ phức tạp của không gian có thể được tối ưu hóa bằng cách sử dụng danh sách kề hoặc cấu trúc dữ liệu hàng đợi.
