Thuật toán Dijkstra trong Python & C++ (Thí dụ)

Đường đi ngắn nhất hay khoảng cách ngắn nhất là gì?

Đường đi từ đỉnh nguồn đến đỉnh đích có chi phí nhỏ nhất được gọi 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ừ nguồn đến đích. Trong số các tuyến đường này, nếu có một tuyến đường có chi phí nhỏ nhất, ta gọi đó là đường đi ngắn nhất.

Ở đây, "chi phí" có nghĩa là số lượng nút trong tuyến đường hoặc tổng chi phí trên mỗi cạnh. Một đường đi có thể có một hoặc nhiều cạnh. Kết nối giữa hai đỉnh được gọi là "cạnh". Có nhiều loại thuật toán tìm đường đi ngắn nhất, chẳng hạn như thuật toán Dijkstra và thuật toán Bellman-Ford.

Ở đây, chúng ta sẽ thảo luận về thuật toán Dijkstra. Hãy xem xét đồ thị có trọng số sau:

Đồ thị có trọng số vô hướng

• Thuật ngữ “có trọng số” (weighted) biểu thị chi phí di chuyển từ nút này sang nút khác. Ví dụ, di chuyển từ nút 1 sang nút 2, chi phí hay trọng số là 1.
• Đường đi giữa nút 1 và nút 2 được gọi là cạnh.
• "Không định hướng" có nghĩa là bạn có thể di chuyển từ 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, chúng sẽ là:

Trong bốn tuyến đường này, ta thấy tuyến đường đầu tiên có chi phí là 7. Vì vậy, đây là con đường ngắn nhất xét về chi phí.

Con đường ngắn nhất

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ó hướng và không hướng có trọng số. Thuật toán này được gọi là tham lam vì nó luôn chọn nút ngắn nhất hoặc gần nhất từ ​​gốc tọa độ. Thuật ngữ “tham lam” có nghĩa là trong một tập hợp các kết quả, thuật toán sẽ chọn kết quả tốt nhất.

Ở đây, chúng ta đang cố gắng tìm đường đi 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 tất cả các đường đi ngắn nhất từ ​​một nút nguồn 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 thực hiện từng bước. Nó hoạt động như sau:

Bước 1) Khởi tạo nút đầu tiên với chi phí bằng 0 và các nút còn lại với chi phí vô hạn.
Bước 2) Duy trì một mảng hoặc danh sách để lưu trữ track trong số các nút đã được truy cập.
Bước 3) Cập nhật chi phí nút bằng chi phí tối thiểu. Điều này 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 dẫn (được minh họa 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 duyệt qua.

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 thuật toán Dijkstra và BFS-DFS là Dijkstra là thuật toán tìm đường đi ngắn nhất, trong khi BFS và DFS là các thuật toán tìm đường đi tổng quát. Trong trường hợp tổng quát, BFS và DFS không xem xét chi phí cạnh khi tìm đường đi. Do đó, các thuật toán này không thể đảm bảo đường đi ngắn nhất.

Minh họa cách thức hoạt động của thuật toán BFS trên lưới 2D.

Thuật toán, hiển thị bản trình diễn 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.

Chúng ta hãy xem một ví dụ về đồ thị:

Ở đây, thuật toán BFS tìm đường đi ở cấp độ 2. BFS duyệt đồ 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à đi qua tất cả các nút liền kề 2, 3, 4.

Bước 2) Đánh dấu các nút 2, 3, 4 là cấp độ 1 và thăm các nút liền kề của chúng. Nó sẽ tiếp tục khám phá tất cả các nút liền kề cho đến khi đến 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 dựa trên số lượng cạnh. DFS thực hiện như 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ề thuật toán Dijkstra, nó 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.

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 toán trọng số. Nó sẽ không tìm kiếm tất cả các đường đi có thể. Chúng ta hãy minh họa 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 ban đầu bằng 0. Gán “Thông tin” đến các nút còn lại. Điều đó có nghĩa là không có đường dẫn nào tồn tại giữa nút nguồn và nút đó, hoặc đường dẫn đó chưa được đi qua.

Bước 2) Khi bạn chọn nút 1, nó sẽ được đánh dấu là đã được thăm. 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 ta có thể cập nhật chi phí của mỗi nút bằng công thức trên. Ví dụ, chúng ta đang ở nút 1 và cần cập nhật chi phí của các nút liền kề 2, 3, 4. Sau khi cập nhật, chi phí sẽ trông như thế này:

Bước 3) Đối với nút “2”, các nút lân cận là 6 và 3. Chúng ta cập nhật chi phí tại “6” bằng cách so sánh vô cực (giá trị hiện tại) với chi phí của nút 2 cộng với chi phí đường đi 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, bằng cách 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, ta sẽ cập nhật chi phí của nút 7. Đó là 8. Vì vậy, ta tìm một đường đi từ nút 1 đến nút 7, và đó là 1→3→7. Chi phí là 8.

Bước 5) Đối với nút 4, chúng ta sẽ cập nhật chi phí của nút liền kề tương ứng. Vì vậy, nút “5” sẽ có chi phí được cập nhật là 8. Sau bước 4 và 5, kết quả sẽ trông như thế này:

Hiện tại, đường đi 1-3-7 có chi phí là 8 (trước đây). Nút “7” không được đánh dấu là đã ghé thăm vì ta có thể đến nút “7” từ nút “6”. Đường đi “1-2-6” có chi phí là 4. Vì vậy, đường đi 1-2-6-7 sẽ có chi phí là 7.

Vì 7 < 8, đườ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 đó là 1-3-7, và chi phí là 8. Vì vậy, đồ thị cuối cùng sẽ có dạng như sau:

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.

Biệt danh Code Thuật toán Dijkstra

Đây là mã giả của thuật toán Dijkstra:

Dijkstra(G, S):
  for each vertex V in G
    distance[V] <- Infinity
    previous[V] <- NULL
    if V does not equal S, then,
      (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
    U <- Extract the MIN from Q
    For each unvisited adjacent V of U
      TotalDistance <- distance[U] + edge_cost(U, V)
      if TotalDistance is less than distance[V], then
        distance[V] <- TotalDistance
        previous[V] <- 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à đoạn 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] && 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] && graph[U][j] &&
          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 PythonĐây là đoạn 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] <= _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 < 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

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 ứng dụng. Trong số đó, nó được sử dụng rộng rãi trong lĩnh vực mạng máy tính. Dưới đây là một số ứng dụng thực tế của thuật toán Dijkstra:

Dijkstra trong Google Bản đồ: Thuật toán này là nền tảng để tìm đường đi ngắn nhất, như chúng ta có thể thấy từ đoạn mã đầu ra ở trên.

Google Ứng dụng này 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 đã được sửa đổi. Khi bạn chọn điểm đến, nó sẽ hiển thị cho bạn nhiều đường dẫn khác nhau. Google Bản đồ. Trong số các tuyến đường này, một số được sắp xếp cho người dùng. Các tuyến đường này được chọn dựa trên "thời gian". Vì vậy, "thời gian" là chi phí cạnh cho tuyến đường ngắn nhất.

Thuật toán Dijkstra trong định tuyến IP: Định tuyến IP IP routing là thuật ngữ mạng. Nó mô tả cách 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. Các đường dẫn này bao gồm bộ định tuyến, máy chủ và các thiết bị khác. 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 ra đường dẫn 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 cập nhật, chúng phải tính toán lại tất cả các đường dẫn. Tại 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 tìm được đường đi ngắn nhất trong đồ thị có các cạnh âm. Thuật toán Dijkstra tuân theo các nguyên tắc 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, Đồ thị có ba đỉnh. Thuật toán Dijkstra sẽ chạy trên đồ thị 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à nút đã được ghé thăm 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 là vô cực, vì đường đi ngắn nhất vẫn chưa được tính toán. Do đó, 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 (phương pháp tham lam).

Bước 4) Cập nhật khoảng cách từ đỉnh nguồn “1” đến “2”. Trọng lượng hiện tại sẽ là 5 (5 < vô cực). Tương tự, cập nhật khoảng cách từ nút “1” đến “3” với trọng lượng là 3.

Bước 5) Bây giờ, nếu ta kiểm tra khoảng cách ngắn nhất từ ​​nút “1”, 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à đã được thăm. Tương tự, nút “3” cũng sẽ được đánh dấu là đã được thăm vì khoảng cách ngắn nhất là 3.

Tuy nhiên, nếu quan sát kỹ, ta thấy có một đường đi 1-3-2 chỉ tốn 2 chi phí. Nhưng thuật toán Dijkstra lại cho thấy khoảng cách ngắn nhất từ ​​nút “1” đến nút “2” là 5. Như vậy, thuật toán Dijkstra đã không tính toán được khoảng cách ngắn nhất một cách chính xác. Lý do là vì Dijkstra là một thuật toán tham lam. Do đó, một khi một nút đã được đánh dấu là đã thăm, nó sẽ không được xem xét lại, mặc dù có thể có một đường đi ngắn hơn. Vấn đề này chỉ xảy ra khi các cạnh có chi phí âm hoặc trọng số âm.

Thuật toán Dijkstra không thể tính toán đường đi ngắn nhất giữa hai nút trong trường hợp này. Do đó, 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 đượ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(V²)Ở đây, thuật ngữ “O” là một ký hiệu đưa ra giả định cho thuật toán Dijkstra.

Chúng ta có thể lưu trữ đồ thị bằng cách sử dụng "hàng đợi ưu tiên". Hàng đợi ưu tiên là một 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ó độ ưu tiên cao. Khi đó độ 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(V²), 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.

Câu Hỏi Thường Gặp