Dijkstra là giữa những thuật toán rất danh tiếng trong giới lập trình. Nghe tới những bài toán tương quan tới tìm lối đi ngắn độc nhất là nghĩ ngay tới thuật toán Dijkstra.

Bạn đang xem:

*

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


Tổng quan tiền thuật toán Dijkstra

Trước khi đi vào chi tiết nội dung thuật toán, họ cần đề nghị hiểu mọi thuật ngữ sau:

Graph (đồ thị): Đồ thị là một cấu tạo dữ liệu phi tuyến đường tính được định nghĩa là G = (V, E), trong V là tập hợp hữu hạn những đỉnh (node), E là tập hòa hợp hữu hạn các cạnh, cạnh là một đường nối giữa hai node cùng với nhau.Weighted graph (đồ thị có trọng số): Tương từ bỏ như thứ thị làm việc trên, chỉ không giống là mỗi cạnh sẽ được gán thêm một trọng số. Vẻ bên ngoài như thuộc một khoảng cách đi trường đoản cú A mang lại B, tuy thế đi đường đẹp thì cấp tốc hơn, đường làng các ổ con gà thì chậm rãi hơn.Connected graph (đồ thị liên thông): Một đồ gia dụng thị được hotline là liên thông (connected) giả dụ có lối đi giữa đa số cặp đỉnh minh bạch của đồ vật thị. Ngược lại, đồ thị này được call là ko liên thông

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

Cho một đồ vật thị bao gồm trọng số (đặt thương hiệu là thứ thị G). Mục tiêu là tìm lối đi ngắn nhất xuất phát từ một đỉnh mang đến trước đến các đỉnh còn sót lại của trang bị thị G.

Xem thêm: Hướng Dẫn Đường Đi Chùa Bà Châu Đốc An Giang Từ A, Cùng Khám Phá Địa Điểm Núi Sam

*

Đồ thị G tất cả các điểm lưu ý sau:

Gồm tập hợp các đỉnh (V)Tập hợp những cạnh (E). Trong số đó ký hiệu (q,r) là trình diễn một cạnh nối thân hai đỉnh q với r, cost(q,r) thì thể hiện trọng số của cạnh đó.

Ý tưởng triển khai thuật toán Dijkstra

Thuật toán Dijkstra dựa vào nguyên tắc sút bớt. Trong các số đó các giá trị đúng đắn hơn vẫn dần sửa chữa một giá trị gần đúng với khoảng cách đúng đắn cho 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ầu tính lớn hơn nhiều khoảng cách thực và sẽ dần sửa chữa bằng giá chỉ trị nhỏ tuổi nhất của giá trị cũ bằng độ nhiều năm của một đường new tìm được.

Thuật toán thực hiện hàng chờ ưu tiên kết phù hợp với thuật toán tham lam lựa chọn đỉnh ngay sát nhất không được xử lý và tiến hành quá trị giảm sút này trên tất cả các cạnh mà nó để ý qua.

Giả thuật công việc thực hiện:

Bước 1: Đánh vệt tất các node dự kiến: Đặt khoảng cách từ nút mối cung cấp tới nút 0 là nguồn, cùng đặ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):

Trích xuất nút N là nút có tầm khoảng cách nhỏ tuổi nhấtThêm links tới nút N vào cây đường đi ngắn nhấtSau đó triển khai tối ưu những đường đi cạnh N bằng phương pháp thử kéo dài cạnh

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

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

Dưới đó là code minh họa bởi C++

#include #include #include #include using namespace std; // Data structure lớn store a graph edgestruct Edge int source, dest, weight;; // Data structure khổng lồ store a heap nodestruct Node int vertex, weight;; // A class khổng lồ represent a graph objectclass Graphpublic: // a vector of vectors of `Edge` to represent an adjacency menu vector> adjList; // Graph Constructor Graph(vector const &edges, int n) // resize the vector lớn hold `n` elements of type vector adjList.resize(n); // địa chỉ edges lớn the directed graph for (Edge const &edge: edges) // insert at the over adjList.push_back(edge); ; void printPath(vector const &prev, int i, int source) if (i rhs.weight; }; // Run Dijkstra’s algorithm on the given graphvoid findShortestPaths(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); // phối initial distance from the source to `v` as infinity vector dist(n, INT_MAX); // distance from the source to lớn itself is zero dist = 0; // boolean array to lớn 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 & return the best vertex Node node = min_heap.top(); min_heap.pop(); // get the vertex number int u = node.vertex; // vày for each neighbor `v` of `u` for (auto i: graph.adjList) { 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 hợp của thuật toán: O(E.log(V))


Chuyên mục: Du lịch