Thuật toán Dijkstra là gì và cách giải trong ngôn ngữ lập trình C++

Thuật toán tìm đường đi ngắn nhất Dijkstra là gì và lịch sử ra đời

Đây là thuật toán được ra đời bởi nhu cầu tìm kiếm giải pháp cho việc tìm kiếm đường đi từ thành phường này tới thành phường khác của con người một cách ngắn nhất. Nó được ra đời chính thức vào năm 1959 bởi nhà khoa học máy tính ông Dijkstra.

Thuật toán Dijkstra tìm đường đi ngắn nhất khắc phục bài toán đường đi ngắn nhất từ một điểm tới những điểm còn lại của đồ thị.

Ví dụ về thuật toán Dijkstra

Ví dụ, để trình diễn đường đi ngắn nhất từ thành phường A tới thành phường B, chúng ta tiêu dùng những đỉnh của đồ thị để thị phạm những thành phường và những cạnh để trình diễn những đường nối giữa chúng. Trọng số những cạnh sẽ được xem như độ dài của những con đường, vì vậy mà chúng ko âm, nhờ đó thuật toán sẽ chỉ ra con đường ngắn nhất.

Trọng số ko âm những cạnh mang tính tổng thể hơn là khoảng cách hình học giữa Hai định, vì vậy thuật toán sẽ với tính chuẩn xác cao hơn.

Dijkstra thường được ứng dụng trong bộ định tuyến với một chương trình con trong một hệ thống định vị toàn cầu hay còn gọi là GPS.

So sánh thuật toán dijkstra và bellman-ford cơ bản

Để so sánh Hai loại thuật toán tìm đường đi ngắn nhất, trước hết cần hiểu được khái niệm của những loại thuật toán này ra sao. Về tổng thể, trong giới kỹ thuật tồn tại 3 dạng thuật toán tìm đường đi ngắn nhất:

  • Thuật Bellman-Ford
  • Thuật Dijkstra
  • Thuật Floyd-Warshall.

Tuy nhiên, thuật toán Floyd còn tiêu dùng để tìm chu trình trong một đồ thị, do đó, sẽ ko kể sâu trong bài viết này mà ta chỉ tập trung vào Hai thuật toán tìm đường đi ngắn nhất Dijkstra và Bellman-Ford.

Sơ lược về thuật toán Bellman-Ford và thao tác tìm đường đi ngắn nhất

Đây là thuật toán sử dụng nhằm khắc phục bài toán đường đi ngắn nhất một nguồn (single source), đồ thị trọng số với âm.

Ý tưởng của thuật toán được xét tới lúc đồ thị ko tồn tại trọng số âm, tức là đường đi ngắn nhất với tồn tại và luôn như thế.

Thuật toán này sẽ lặp lại nhiều lần và ở mỗi vòng lặp, chủ thể sẽ đi qua tất cả những cạnh (u,v) trên đồ thị. Những nhà nghiên cứu nhận xét rằng một đường đi ngắn nhất tùy ý sẽ ko với điểm được đi lại thêm một lần nào nữa, tương tự đường đi ngắn nhất sẽ là N-1, trong đó N- Một là vòng lặp thực hiện trong thực nghiệm.

Bellman-Ford thường được lưu ở dạng danh sách cạnh và với những lưu ý sau trong thuật toán:

  • Khái niệm W[u,v] là trọng số cạnh nối đỉnh u tới đỉnh v.
  • Khái niệm mảng D[u] là đường đi ngắn nhất từ s tới u.
  • Độ phức tạp của thuật toán là O(N*M) trong một vòng lặp được thực hiện N – Một lần và mỗi lần tương tự ta sẽ xử lý tất cả những cạnh trong đồ thị.

Mức độ xử lý tìm đường đi ngắn nhất của thuật toán khá thuần tuý bằng cách truy vết từ đỉnh u theo mảng trace và trái lại điểm khởi đầu S, code như sau:

    while (u != -1) { // truy vết ngược từ u về S

        path.push_back(u);

        u = trace[u];

    }

    reverse(path.begin(), path.end()); // cần reverse vì đường đi lúc này là từ u về S

    

    return path;

}

Sơ lược thuật toán Dijkstra tìm đường đi ngắn nhất

Đây là thuật toán sử dụng nhằm khắc phục bài toán đường đi ngắn nhất một nguồn (single source), đồ thị trọng số ko âm.

Ý tưởng bài toán cũng tương tự Bellman-Ford, thuật toán Dijkstra cũng tối giản đường đi bằng cách xét những cạnh và so sánh Hai đường đi sẵn với với đường qua cả 3 đỉnh.

Nguyên lý hoạt động bằng cách duy trì một tập hợp những đỉnh trong đó đã được biết chắc đường đi ngắn nhất. Qua từng bước, thuật toán sẽ chọn ra một đỉnh mà kiên cố đã được tối ưu hóa cao nhất. Sau N bước, tất cả những đỉnh đều được chọn và mọi đường đi tìm được đều sẽ là ngắn nhất.

Dijkstra thường được lưu dưới dạng danh sách kề và với những lưu ý sau:

  • D[u] là đường ngắn nhất từ s tới u.
  • W[u,v] là trọng số cạnh trên phố đi từ u tới v.
  • P[u] là mảng đánh dấu những đỉnh u với tất cả trị giá ban sơ đều là False.
  • Độ phức tạp của thuật toán là O(N^2 + M)

Để tìm lại đường đi ngắn nhất từ S về u, ta sẽ truy vết từ đỉnh u theo mảng trace và về trái lại S, code như sau:

    while (u != -1) { // truy vết ngược từ u về S

        path.push_back(u);

        u = trace[u];

    }

    reverse(path.begin(), path.end()); // cần reverse vì đường đi lúc này là từ u về S

    

    return path;

}

Tương tự, thông qua sơ lược Hai thuật toán, bạn với thể phân biệt được Dijkstra và Bellman-Ford thông qua 4 yếu tố chính:

  • Bài toán khắc phục vấn đề tìm đường đi ngắn nhất như thế nào
  • Độ phức tạp ra sao
  • Sở hữu sử dụng được cho trọng số âm hay ko
  • Sở hữu tìm được chu trình âm hay ko.

Cách triển khai thuật toán Dijkstra Python cơ bản

Như đã biết, thuật toán Dijkstra được ứng dụng với mục đích tìm đường đi ngắn nhất giữa những nút trong đồ thị. Phương tiện này được sử dụng trong thực tiễn dưới những sản phẩm tìm được tự động giữa những vị trí thực tế, ví dụ như Google Maps là một sản phẩm của thuật toán Dijkstra.

Minh họa cách triển khai thuật toán

Ưu điểm của thuật toán Dijkstra là với thể giúp con người tìm ra con đường ngắn nhất cho dù giả thiết tầm giá đi qua mỗi đường là khác nhau. Hơn nữa, thuật toán Dijkstra với một phương thức xử lý đặc trưng đó là khắc phục những nút sắp nhất để với thể cho ra một số bước tắt để tìm đường đi ngắn nhất.

Sau đây là cách triển khai thuật toán Dijkstra C++ thuần tuý nhất:

from head import *

from collections import defaultdict

def dijkstra(edges, strat_node, end_node):

    g = defaultdict(list) 

    for start, end, weight in edges: 

        g[start].append((weight, end)) 

    q, visited = [(0, strat_node,())], set()

    while q:        

        (cost,v1,path) = heappop(q)

        if v1 not in visited:

            visited.add(v1)

            path = (v1, path)            

            if v1 == end_node:

                return (cost, path)

            for c, v2 in g.get(v1, ()):

                if v2 not in visited:

                    heappush(q, (cost+c, v2, path))

        print (q)   

    return float(“inf”)

if __name__ == “__main__”:

    

    edges = [

        (“A”, “B”, 7),

        (“A”, “D”, 5),

        (“B”, “C”, 8),

        (“B”, “D”, 9),

        (“B”, “E”, 7),

        (“C”, “E”, 5),

        (“D”, “E”, 7),

        (“D”, “F”, 6),

        (“E”, “F”, 8),

        (“E”, “G”, 9),

        (“F”, “G”, 11)

    ]

    

    print (“=== Dijkstra ===”)

    print (dijkstra(edges, “A”, “G”))

 === Dijkstra ===

Source code thuật toán dijkstra cần chú ý điều gì

Lúc khởi đầu tìm hiểu thuật toán Dijkstra phần đông những bạn đều sẽ thấy phức tạp bởi nó là tính toán của một chuỗi chu kỳ vòng lặp trông khá rối rắm, tuy nhiên, tóm tắt thuật toán với thể thực hiện 5 bước thuần tuý sau:

  • Bước 1: Đánh dấu đỉnh nguồn (đỉnh mở đầu) là $0$ và những đỉnh còn lại là “vô cùng”.
  • Bước 2: Gọi đỉnh chưa xét với trị giá đánh dấu min là $C$ (current node).
  • Bước 3: Mỗi đỉnh kề $N$ với đỉnh $C$, ta cùng trị giá đang đánh dấu của đỉnh $C$ với trọng số của cạnh nối đỉnh Current node cùng đỉnh kề, nếu kết quả nhỏ hơn trị giá đang đánh dấu ở $N$ thì ta cập nhật trị giá mới đó cho đỉnh.
  • Bước 4: Đánh dấu đỉnh $C$ đã xét.
  • Bước 5: Tiếp tục vòng lặp tại bước Hai cho tới lúc ko còn đỉnh chưa xét.

Ứng dụng thực tiễn của thuật toán Dijkstra trong đời sống hiện nay

Ứng dụng tìm đường ngắn nhất trên bản đồ

Theo đó, những ứng dụng tìm kiếm đường đi và chỉ đường hiện nay đều sẽ hiện nhiều lựa chọn với những trị số thời kì để bạn lựa chọn ra con đường ngắn nhất từ điểm xuất phát tới điểm tới dựa trên những hiển thị và những yếu tố tác động từ vệ tinh, từ đó ứng dụng thuật toán Dijkstra C++ để hiển thị đường.

Ứng dụng google map với thuật toán Dijkstra

Ứng dụng trong mạng xã hội

Những trang doanh nghiệp kinh doanh nhỏ lẻ hay những trang mạng xã hội với hướng dẫn đường đi cho người theo dõi cũng ứng dụng thuật toán Dijkstra để nhúng đường đi của doanh nghiệp lên mạng xã hội. Qua đó, người tiêu dùng chỉ cần truy cập trang facebook của doanh nghiệp, sử dụng chức năng chỉ đường là sẽ tự động được tính toán và dẫn ra con đường ngắn nhất.

Ứng dụng trong hệ thống thông tin di động điện tử

Ngoài việc tìm đường đi thực tế, một số hệ thống thông tin di động còn ứng dụng thuật toán này để với thể truyền tải thông tin nhanh hơn lúc với kết nối nội bộ giữa những đỉnh, những đỉnh này với thể là GPS hay Airdrop, miễn sao với kết nối thì thuật toán sẽ tìm được đường nhanh nhất để truyền tải thông tin bạn muốn.

Ngoài ra, việc sử dụng internet cũng là điều kiện để những hacker sử dụng dấu vết của bạn, kết nối những đỉnh và truy tìm ra những thông tin được kết nối cũng như đường chuẩn xác và ngắn nhất tới địa điểm mà bạn đang truy cập mạng.

Ứng dụng trong kỹ thuật của ngành hàng ko vũ trụ

Tương tự hệ thống liên lạc vận tải mặt đất, thuật toán Dijkstra hết sức hữu dụng lúc những phi công phải dựa trên bản đồ hiển thị trong quá trình lái phi cơ được tích hợp thông qua thuật toán, tránh việc tìm đường dựa trên giác quan gây ra những sơ sót nghiêm trọng tới tính mệnh cũng như những hệ lụy nặng nề khác.

Tính chất của ngành hàng ko là phải bay theo quỹ đạo được định sẵn bởi thuật toán, nếu bạn cố ý bay chệch đường bay được định sẵn, thuật toán sẽ trở nên lộn xộn và dễ vượt ngoài tầm kiểm soát.

Lời kết

Qua những thông vừa rồi được nêu trên đây về thuật toán Dijkstra được ứng dụng nhiều trong những cuộc thi lập trình, ứng dụng khoa học kỹ thuật đời sống để khắc phục bài toán tìm đường đi ngắn nhất một cách hiệu quả. Kỳ vọng đã gỡ rồi được phần nào cho những bạn lập trình viên đang học tới thuật toán này.

Leave a Comment

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *