BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT VỚI GIẢI THUẬT DIJKSTRA, CÁC THUẬT TOÁN VỀ TÌM ĐƯỜNG ĐI NGẮN NHẤT

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

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

Ưu điểm của thuật toán Dijkstra là có thể giúp con người tìm ra con đường ngắn nhất cho dù giả định chi phí đi qua mỗi đường là khác nhau. Hơn nữa, thuật toán Dijkstra có một phương thức xử lý đặc biệt đó là giải quyết các nút gần nhất để có 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++ đơn giản 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.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 (“A >> G:”)

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

 === Dijkstra ===

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

Khi bắt đầu tìm hiểu thuật toán Dijkstra đa số các 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ắc rối, tuy nhiên, tóm tắt thuật toán có thể thực hiện 5 bước đơn giản sau:

Ứ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 đó, các ứ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 các trị số thời gian để bạn lựa chọn ra con đường ngắn nhất từ điểm xuất phát đến điểm đến dựa trên những hiển thị và các yếu tố tác động từ vệ tinh, từ đó áp dụng thuật toán Dijkstra C++ để hiển thị đường.

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

Các trang doanh nghiệp kinh doanh nhỏ lẻ hay các trang mạng xã hội có hướng dẫn đường đi cho người theo dõi cũng áp 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 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 để có thể truyền tải thông tin nhanh hơn khi có kết nối nội bộ giữa các đỉnh, các đỉnh này có thể là GPS hay Airdrop, miễn là có 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.

Bên cạnh đó, việc sử dụng internet cũng là điều kiện để các hacker sử dụng dấu vết của bạn, kết nối các đỉnh và truy tìm ra những thông tin được kết nối cũng như đường chính xác và ngắn nhất đến đị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 không vũ trụ

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

Tính chất của ngành hàng không 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 áp dụng nhiều trong các cuộc thi lập trình, ứng dụng khoa học công nghệ đời sống để giải quyết bài toán tìm đường đi ngắn nhất một cách hiệu quả. Hy vọng đã gỡ rồi được phần nào cho các bạn lập trình viên đang học đến thuật toán này.

Dijkstra là một trong những thuật toán rất nổi tiếng trong giới lập trình. Nghe tới những bài toán liên quan tới tìm đường đi ngắn nhất là nghĩ ngay tới thuật toán Dijkstra.

Dijkstra là thuật toán được đặt tên theo nhà khoa học máy tính người Phần Lan, người đã phát minh ra nó. Thuật toán này nhằm mục đích tìm đường đi ngắn nhất trong đồ thị có cạnh với trọng số dương.

Tổng quan thuật toán Dijkstra

Trước khi đi vào chi tiết nội dung thuật toán, chúng ta cần phải hiểu những thuật ngữ sau:

Thuật toán Dijkstra giải quyết bài toán gì?

Cho một đồ thị có trọng số (đặt tên là đồ thị G). Mục tiêu là tìm đường đi ngắn nhất từ một đỉnh cho trước đến các đỉnh còn lại của đồ thị G.

Đồ thị G có các đặc điểm sau:

Ý tưởng thực hiện thuật toán Dijkstra

Thuật toán Dijkstra dựa trên nguyên tắc giảm bớt. Trong đó các giá trị chính xác hơn sẽ dần thay thế một giá trị gần đúng với khoảng cách chính xác cho đến khi đạt được khoảng cách ngắn nhất. Khoảng cách gần đúng tới mỗi định được ước tính lớn hơn nhiều khoảng cách thực và sẽ dần thay thế bằng giá trị nhỏ nhất của giá trị cũ bằng độ dài của một đường mới tìm được.

Thuật toán sử dụng hàng đợi ưu tiên kết hợp với thuật toán tham lam chọn đỉnh gần nhất chưa được xử lý và thực hiện quá trị giảm bớt này trên tất cả các cạnh mà nó duyệt qua.

Xem thêm: 7 loài bướm hiếm nhất thế giới ở trung quốc, 7 loài bướm hiếm nhất thế giới

Giả thuật các bước thực hiện:

Bước 1: Đánh dấu tất các node dự kiến: Đặt khoảng cách từ nút nguồn tới nút 0 là nguồn, và đặt là vô hạn với các nút khác.

Bước 2: Tiến hành chạy lặp (loop):

Mã nguồn c++ minh họa thuật toán tìm đường đi ngắn nhất

Thuật toán có thể được implement bởi bất kỳ ngôn ngữ nào: C++, Java, hay Python…

Dưới đây là code minh họa bằng C++

#include #include #include #include using namespace std; // Data structure to store a graph edgestruct Edge { int source, dest, weight;}; // Data structure to store a heap nodestruct Node { int vertex, weight;}; // A class to represent a graph objectclass Graph{public: // a vector of vectors of `Edge` to represent an adjacency list vector> adj
List; // Graph Constructor Graph(vector const &edges, int n) { // resize the vector to hold `n` elements of type vector adj
List.resize(n); // add edges to the directed graph for (Edge const &edge: edges) { // insert at the end adj
List.push_back(edge); } }}; void print
Path(vector const &prev, int i, int source){ if (i rhs.weight; }}; // Run Dijkstra’s algorithm on the given graphvoid find
Shortest
Paths(Graph const &graph, int source, int n){ // create a min-heap and push source node having distance 0 priority_queue, comp> min_heap; min_heap.push({source, 0}); // set initial distance from the source to `v` as infinity vector dist(n, INT_MAX); // distance from the source to itself is zero dist = 0; // boolean array to track vertices for which minimum // cost is already found vector done(n, false); done = true; // stores predecessor of a vertex (to a print path) vector prev(n, -1); // run till min-heap is empty while (!min_heap.empty()) { // Remove and return the best vertex Node node = min_heap.top(); min_heap.pop(); // get the vertex number int u = node.vertex; // do for each neighbor `v` of `u` for (auto i: graph.adj
List) { int v = i.dest; int weight = i.weight; // Relaxation step if (!done && (dist + weight) " edges = { {0, 1, 10}, {0, 4, 3}, {1, 2, 2}, {1, 4, 4}, {2, 3, 9}, {3, 2, 7}, {4, 1, 1}, {4, 2, 8}, {4, 3, 2} }; // total number of nodes in the graph (labelled from 0 to 4) int n = 5; // construct graph Graph graph(edges, n); // run the Dijkstra’s algorithm from every node for (int source = 0; source Kết quả khi chạy chương trình:

Path (0 —> 1): Minimum cost = 4, Route = <0, 4, 1>Path (0 —> 2): Minimum cost = 6, Route = <0, 4, 1, 2>Path (0 —> 3): Minimum cost = 5, Route = <0, 4, 3>Path (0 —> 4): Minimum cost = 3, Route = <0, 4>Path (1 —> 2): Minimum cost = 2, Route = <1, 2>Path (1 —> 3): Minimum cost = 6, Route = <1, 4, 3>Path (1 —> 4): Minimum cost = 4, Route = <1, 4>Path (2 —> 3): Minimum cost = 9, Route = <2, 3>Path (3 —> 2): Minimum cost = 7, Route = <3, 2>Path (4 —> 1): Minimum cost = 1, Route = <4, 1>Path (4 —> 2): Minimum cost = 3, Route = <4, 1, 2>Path (4 —> 3): Minimum cost = 2, Route = <4, 3>Độ phức tạp của thuật toán: O(E.log(V))