Code thuật toán a python
Ta bắt đầu khởi tạo các mảng n phần tử: label, length, prev. Gán label[k] = 1, length[k] = -1 (inf), prev[k] = -1 với k chạy từ 0 -> n – 1. Gán length[first] = 0. Show Nội dung chính
Chọn đỉnh v trong mảng sao cho length[k] là nhỏ nhất. Sau đó gán label[k] = 0 (Đã đánh dấu). Tạo vòng lặp với biến chạy k, xét nếu label[k] = 1 (Chưa đánh dấu) và có đường đi từ v -> k: Nếu length[k] > length[v] + trọng số từ v -> k hoặc length[k] = inf, có nghĩa là nếu ta tìm được 1 đường từ v -> k là nhỏ nhất, hoặc là chưa tìm được đường nào ngắn nhất (inf) => Gán length[k] = length[v] + trọng số v -> k, prev[k] = v (Tạo vết chân đỉnh trước đó). Nếu label[last] = 0 (Đã đánh dấu đỉnh đến), kết thúc vòng lặp. Nếu không thì quay lại bước 2. VD: Ta có 1 đồ thị như sau 2. Viết và chạy thuật toánĐể đơn giản, trong phần này tôi dùng ma trận kề, và mỗi các đỉnh được đặt tên theo số thứ tự 0,1,2. /** * Trong nay, cac dinh khong co canh noi voi nhau se co khoang cach la -1 */ public int[] dijkstra(int[][] graph, int s){ int [] dist = new int[graph.length]; for(int i = 0; i < graph.length; i++){ dist[i] = Integer.MAX_VALUE; } dist[s] = 0; int [] visit = new int[graph.length]; for(int i = 0; i < graph.length; i ++){ int v = closestVertice(graph[s], visit); for(int j = 0; j < graph[v].length; j++){ if (graph[v][j] != -1){ // neu co canh noi giua v va j int currentDist = dist[v] + graph[v][j]; if (currentDist < dist[j]){ dist[j] = currentDist; } } } } return dist; } /** * Chon ra dinh o gan s nhat va danh dau dinh do la da tham * */ public int closestVertice(int[] adjacentVertices, int[] visit){ int closest = -1; int minDist = Integer.MAX_VALUE; for(int i = 0; i < adjacentVertices.length; i ++){ if (visit[i] == 0 && adjacentVertices[i] < minDist){ closest = i; minDist = adjacentVertices[i]; } } visit[closest] = 1; return closest; }Output của thuật toán trên sẽ là: Distance from '0' to '0':0 Distance from '0' to '1':2 Distance from '0' to '2':3 Distance from '0' to '3':4 Distance from '0' to '4':43.Đánh giá độ phức tạpĐộ phức tạp của thuật toán trên sẽ là O(V2). Nếu ta sử dụng một hàng đợi ưu tiên (priority queue), ví dụ như Binary heap, và sử dụng danh sách kề thì độ phức tạp của thuật toán sẽ bị giảm xuống còn O((V+E)∗logV). Nguyên nhân là, với danh sách kề, thời gian để duyệt các cạnh và các đỉnh sẽ là O(E+V) thay vì O(V2) như ma trận kề. Ngoài ra, với binary heap, việc tìm đỉnh gần nhất ở closestVertice(graph[s], visit); sẽ chỉ còn O(1) thay vì O(V). Vì thế ta cần nhập khoảng cách tới các đỉnh xung quanh vào binary heap bằng cách bỏ các đỉnh đó ra khỏi heap rồi thêm lại, cái này mất O(logV). Vậy cuối cùng độ phức tạp sẽ là O((V+E)∗logV). Trên đây là bài viết về "Tìm đường ngắn nhất bằng thuật toán Dijkstra". Tuỳ theo từng yêu cầu cụ thể mà bạn có thể lựa chọn cách làm hợp lý. Đăng bởi: Admin | Lượt xem: 6567 | Chuyên mục: Java Với các bạn sinh viên chuyên ngành công nghệ thông tin, chắc không lạ gì với bài toán tìm đường đi ngắn nhất (Shortest Path Problems) trong đồ thị trọng số nữa. Ở bài viết lần này, mình sẽ giới thiệu bài toán tìm đường đi ngắn nhất và ứng dụng của nó, giải thích giải thuật Dijkstra để giải quyết bài toán trên, viết giải thuật Dijkstra bằng code Ruby . Với các bạn sinh viên chuyên ngành công nghệ thông tin, chắc không lạ gì với bài toán tìm đường đi ngắn nhất (Shortest Path Problems) trong đồ thị trọng số nữa. Ở bài viết lần này, mình sẽ giới thiệu bài toán tìm đường đi ngắn nhất và ứng dụng của nó, giải thích giải thuật Dijkstra để giải quyết bài toán trên, viết giải thuật Dijkstra bằng code Ruby . Giới thiệu bài toán tìm đường đi ngắn nhấtBài toán: Cho một đồ thị trọng số gồm các nodes A,B,C,D,E,F và khoảng cách giữa các nodes tương ứng với các cạnh như hình bên dưới . Tìm đường đi ngắn nhất từ node B đến các node còn lại trong đồ thị? Sau khi giải bài toán, ta được kết quả như sau. Đường đi ngắn nhất từ A đến 5 node còn lại:
Để nói về ứng dụng của việc giải bài toán này, nếu bạn thay các node bằng các giao lộ, và các cạnh của nó là các tuyến đường, ta sẽ có 1 bài toán rất quen thuộc. Bài toán tìm đường đi ngắn nhất đến một địa điểm trên bản đồ. Ví dụ như hình ở trên, bằng cách giải quyết bài toán này, bạn sẽ tìm được lộ trình ngắn nhất để đi từ vị trí của bạn đến Mễ Trì Thượng. Ngoài ra, nếu thay các node bằng các router mạng hoặc các host , chúng ta có bài toán định tuyến đường đi của một hệ thống mạng - loại bài toán cơ bản mà các kỹ sư mạng cần phải biết đến: Có khá nhiều giải thuật được đưa ra để giải quyết bài toán này : Dijkstra's algorithm , Bellman–Ford algorithm, A* search algorithm, Floyd–Warshall algorithm, ..... Tuy nhiên ở bài viết này, mình sẽ giải thích về giải thuật Dijkstra và cách để viết nó bằng code Ruby. Giải thích về giải thuật DijkstraMô tả về giải thuật Dijkstra:
Để giải thích về cách giải thuật Dijkstra hoạt động, mình sẽ sử dụng đồ thị trọng số dưới đây để đi tìm đường đi ngắn nhất từ node C đến mọi node còn lại trong đồ thị : Trong quá trình thuật toán chạy, ta gọi cost(node) là khoảng cách ngắn nhất từ mỗi node đến node C và đánh dấu nó trên hình (giá trị số màu xanh da trời) . Khi thuật toán mới bắt đầu, ta mặc định lưu cost(C) = 0 , cost(A) = cost(B) = cost(D) = cost(E) = infinity. Ta cũng đánh dấu current_node (node đang xét hiện tại) bằng một dấu chấm đỏ trên hình. current_node đầu tiên sẽ là node đích của bài toán - ở đây là C. Thuật toán bắt đầu chạy bằng cách xét tất cả các node kề với current_node (các node được nối trực tiếp với current_node ) , ở đây là A, B và D. Ta sẽ bắt đầu với node B trước và thực hiện 4 bước:
Tương tự với A và D, ta cũng tìm được cost(A) = 1 và cost(D) = 2 . Sau khi xét hết tất cả các node kề với current_node, ta chuyểncurrent_node thành passed_node - tức là node đã được xét rồi. passed_node sẽ được đánh 1 dấu tích xanh trên hình. Bây giờ chúng ta sẽ chọn 1 current_node mới với 2 điều kiện:
Nếu xét trên hình, current_node tiếp theo sẽ là node A . Ta đánh dấu node A với 1 dấu chấm đỏ. Ta tiếp tục giải thuật bằng cách xét các node kề với current_node với điều kiện node kề không được là passed_node . Như vậy ở đây ta chỉ được xét node B .
Đánh dấu node A trở thành passed_node. Ta tiếp tục tìm current_node mới, lần này nó là node D với cost(D) = 2: Có 2 node kề với D là B và E. Xét với node B
Xét với node E
Đánh dấu node D trở thành passed_node. Ta tiếp tục tìm current_node mới, lần này nó là node B với cost(B) = 4 : Chỉ còn 1node kề với B là E. Xét với node E
Giờ chúng ta không còn node nào để check nữa. Đánh dấu node E trở thành passed_node và kết thúc thuật toán. Vậy ta có kết quả của thuật toán với đường đi ngắn nhất từ C đến các điểm còn lại là:
3. Giải thuật Diijkstra với code RubyMình đã giải thích rất rõ cách hoạt động của giải thuật Dijkstra rồi. Nên việc triển khai nó trong code Ruby khá dễ hiểu. Đây là sourecode Ruby về giải thuật này: class Graph # Constructor def initialize @g = {} # the graph // {node => { edge1 => weight, edge2 => weight}, node2 => ... @nodes = Array.new @INFINITY = 1 << 64 end def add_edge(s,t,w) # s= source, t= target, w= weight if (not @g.has_key?(s)) @g[s] = {t=>w} else @g[s][t] = w end # Begin code for non directed graph (inserts the other edge too) if (not @g.has_key?(t)) @g[t] = {s=>w} else @g[t][s] = w end # End code for non directed graph (ie. deleteme if you want it directed) if (not @nodes.include?(s)) @nodes << s end if (not @nodes.include?(t)) @nodes << t end end # based of wikipedia's pseudocode: http://en.wikipedia.org/wiki/Dijkstra's_algorithm def dijkstra(s) @d = {} @prev = {} @nodes.each do |i| @d[i] = @INFINITY @prev[i] = -1 end @d[s] = 0 q = @nodes.compact while (q.size > 0) u = nil; q.each do |min| if (not u) or (@d[min] and @d[min] < @d[u]) u = min end end if (@d[u] == @INFINITY) break end q = q - [u] @g[u].keys.each do |v| alt = @d[u] + @g[u][v] if (alt < @d[v]) @d[v] = alt @prev[v] = u end end end end # To print the full shortest route to a node def print_path(dest) if @prev[dest] != -1 print_path @prev[dest] end print ">#{dest}" end # Gets all shortests paths using dijkstra def shortest_paths(s) @source = s dijkstra s puts "Source: #{@source}" @nodes.each do |dest| puts "\nTarget: #{dest}" print_path dest if @d[dest] != @INFINITY puts "\nDistance: #{@d[dest]}" else puts "\nNO PATH" end end end end gr = Graph.new gr.add_edge("a","b",5) gr.add_edge("b","c",3) gr.add_edge("c","d",1) gr.add_edge("a","d",10) gr.add_edge("b","d",2) gr.add_edge("f","g",1) gr.shortest_paths("a")Nguồn: https://viblo.asia/p/bai-toan-tim-duong-di-ngan-nhat-voi-giai-thuat-dijkstra-eW65GRxLlDO |