Dijkstra 算法 · Programiz 中文系列教程

# Dijkstra 算法 > 原文： [https://www.programiz.com/dsa/dijkstra-algorithm](https://www.programiz.com/dsa/dijkstra-algorithm) #### Dijkstra 算法使我們能夠找到圖形中任意兩個頂點之間的最短路徑。它與最小生成樹不同，因為兩個頂點之間的最短距離可能不包括圖形的所有頂點。 * * * ## Dijkstra 算法的工作原理 Dijkstra 算法的工作原理是，頂點`A`和`D`之間的最短路徑`A -> D`的任何子路徑`B -> D`也是頂點`B`和`D`之間的最短路徑。 ![shortest subpath property is used by dijkstra's algorithm](https://img.kancloud.cn/0c/67/0c67f7cf0e1067293ef15d67e103d389_1460x520.png "Subpaths - Dijkstra's Algorithm") 每個子路徑是最短路徑 Djikstra 在相反的方向上使用了此屬性，即我們高估了每個頂點到起始頂點的距離。然后，我們訪問每個節點及其鄰居，以找到到這些鄰居的最短子路徑。該算法使用貪婪方法，因為我們找到了下一個最佳解決方案，希望最終結果是整個問題的最佳解決方案。 * * * ## Dijkstra 算法的示例從一個示例開始，然后考慮該算法會更容易。 ![Start with a weighted graph](https://img.kancloud.cn/39/37/39373f293428bcc7b68a68a1d632a272_1460x612.png "Dijkstra's algorithm steps") 從加權圖開始 ![Choose a starting vertex and assign infinity path values to all other devices](https://img.kancloud.cn/17/2d/172da741c22eb1240348a508f53950c3_1460x612.png "Dijkstra's algorithm steps") 選擇一個起始頂點并將無限路徑值分配給所有其他設備 ![Go to each vertex and update its path length](https://img.kancloud.cn/c6/6e/c66e127e70c5b2c46f42485e349b0ad2_1460x612.png "Dijkstra's algorithm steps") 轉到每個頂點并更新其路徑長度 ![If the path length of the adjacent vertex is lesser than new path length, don't update it](https://img.kancloud.cn/07/3c/073c650767b281c1c698f1f8a2cd20e5_1460x612.png "Dijkstra's algorithm steps") 如果相鄰頂點的路徑長度小于新路徑的長度，請不要更新它 ![Avoid updating path lengths of already visited vertices](https://img.kancloud.cn/d0/c4/d0c45899cb2f65ca2442d959bb3db0b3_1460x660.png "Dijkstra's algorithm steps") 避免更新已訪問頂點的路徑長度 ![After each iteration, we pick the unvisited vertex with the least path length. So we choose 5 before 7](https://img.kancloud.cn/77/68/7768411e8d5b4c8b5a2cff37cfe06f53_1460x612.png "Dijkstra's algorithm steps") 每次迭代后，我們選擇路徑長度最小的未訪問頂點。所以我們選擇 7 之前的 5 ![Notice how the rightmost vertex has its path length updated twice](https://img.kancloud.cn/9d/25/9d25f684e266fc45b7ccd815b3673860_1460x612.png "Dijkstra's algorithm steps") 注意最右邊的頂點的路徑長度如何更新兩次 ![Repeat until all the vertices have been visited](https://img.kancloud.cn/13/87/13870090338de3bf4c9a3be201a0901e_1460x612.png "Dijkstra's algorithm steps") 重復直到所有頂點都被訪問 * * * ## Djikstra 的算法偽代碼我們需要保持每個頂點的路徑距離。我們可以將其存儲在大小為`v`的數組中，其中`v`是頂點數。我們還希望能夠獲得最短路徑，不僅知道最短路徑的長度。為此，我們將每個頂點映射到最后更新其路徑長度的頂點。算法結束后，我們可以從目標頂點回溯到源頂點以找到路徑。最小優先隊列可用于以最小路徑距離有效接收頂點。 ``` function dijkstra(G, S) for each vertex V in G distance[V] <- infinite previous[V] <- NULL If V != S, add V to Priority Queue Q distance[S] <- 0 while Q IS NOT EMPTY U <- Extract MIN from Q for each unvisited neighbour V of U tempDistance <- distance[U] + edge_weight(U, V) if tempDistance < distance[V] distance[V] <- tempDistance previous[V] <- U return distance[], previous[] ``` * * * ## Dijkstra 算法的代碼下面給出了 Dijkstra 算法在 C++ 中的實現。可以提高[代碼](http://www.reviewmylife.co.uk/blog/2008/07/15/dijkstras-algorithm-code-in-c/)的復雜度，但是抽象方法很容易將代碼與算法相關聯。 ```py # Dijkstra's Algorithm in Python import sys # Providing the graph vertices = [[0, 0, 1, 1, 0, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0]] edges = [[0, 0, 1, 2, 0, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0]] # Find which vertex is to be visited next def to_be_visited(): global visited_and_distance v = -10 for index in range(num_of_vertices): if visited_and_distance[index][0] == 0 \ and (v < 0 or visited_and_distance[index][1] <= visited_and_distance[v][1]): v = index return v num_of_vertices = len(vertices[0]) visited_and_distance = [[0, 0]] for i in range(num_of_vertices-1): visited_and_distance.append([0, sys.maxsize]) for vertex in range(num_of_vertices): # Find next vertex to be visited to_visit = to_be_visited() for neighbor_index in range(num_of_vertices): # Updating new distances if vertices[to_visit][neighbor_index] == 1 and \ visited_and_distance[neighbor_index][0] == 0: new_distance = visited_and_distance[to_visit][1] \ + edges[to_visit][neighbor_index] if visited_and_distance[neighbor_index][1] > new_distance: visited_and_distance[neighbor_index][1] = new_distance visited_and_distance[to_visit][0] = 1 i = 0 # Printing the distance for distance in visited_and_distance: print("Distance of ", chr(ord('a') + i), " from source vertex: ", distance[1]) i = i + 1 ``` ```java // Dijkstra's Algorithm in Java public class Dijkstra { public static void dijkstra(int[][] graph, int source) { int count = graph.length; boolean[] visitedVertex = new boolean[count]; int[] distance = new int[count]; for (int i = 0; i < count; i++) { visitedVertex[i] = false; distance[i] = Integer.MAX_VALUE; } // Distance of self loop is zero distance[source] = 0; for (int i = 0; i < count; i++) { // Update the distance between neighbouring vertex and source vertex int u = findMinDistance(distance, visitedVertex); visitedVertex[u] = true; // Update all the neighbouring vertex distances for (int v = 0; v < count; v++) { if (!visitedVertex[v] && graph[u][v] != 0 && (distance[u] + graph[u][v] < distance[v])) { distance[v] = distance[u] + graph[u][v]; } } } for (int i = 0; i < distance.length; i++) { System.out.println(String.format("Distance from %s to %s is %s", source, i, distance[i])); } } // Finding the minimum distance private static int findMinDistance(int[] distance, boolean[] visitedVertex) { int minDistance = Integer.MAX_VALUE; int minDistanceVertex = -1; for (int i = 0; i < distance.length; i++) { if (!visitedVertex[i] && distance[i] < minDistance) { minDistance = distance[i]; minDistanceVertex = i; } } return minDistanceVertex; } public static void main(String[] args) { int graph[][] = new int[][] { { 0, 0, 1, 2, 0, 0, 0 }, { 0, 0, 2, 0, 0, 3, 0 }, { 1, 2, 0, 1, 3, 0, 0 }, { 2, 0, 1, 0, 0, 0, 1 }, { 0, 0, 3, 0, 0, 2, 0 }, { 0, 3, 0, 0, 2, 0, 1 }, { 0, 0, 0, 1, 0, 1, 0 } }; Dijkstra T = new Dijkstra(); T.dijkstra(graph, 0); } } ``` ```c // Dijkstra's Algorithm in C #include <stdio.h> #define INFINITY 9999 #define MAX 10 void Dijkstra(int Graph[MAX][MAX], int n, int start); void Dijkstra(int Graph[MAX][MAX], int n, int start) { int cost[MAX][MAX], distance[MAX], pred[MAX]; int visited[MAX], count, mindistance, nextnode, i, j; // Creating cost matrix for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (Graph[i][j] == 0) cost[i][j] = INFINITY; else cost[i][j] = Graph[i][j]; for (i = 0; i < n; i++) { distance[i] = cost[start][i]; pred[i] = start; visited[i] = 0; } distance[start] = 0; visited[start] = 1; count = 1; while (count < n - 1) { mindistance = INFINITY; for (i = 0; i < n; i++) if (distance[i] < mindistance && !visited[i]) { mindistance = distance[i]; nextnode = i; } visited[nextnode] = 1; for (i = 0; i < n; i++) if (!visited[i]) if (mindistance + cost[nextnode][i] < distance[i]) { distance[i] = mindistance + cost[nextnode][i]; pred[i] = nextnode; } count++; } // Printing the distance for (i = 0; i < n; i++) if (i != start) { printf("\nDistance from source to %d: %d", i, distance[i]); } } int main() { int Graph[MAX][MAX], i, j, n, u; n = 7; Graph[0][0] = 0; Graph[0][1] = 0; Graph[0][2] = 1; Graph[0][3] = 2; Graph[0][4] = 0; Graph[0][5] = 0; Graph[0][6] = 0; Graph[1][0] = 0; Graph[1][1] = 0; Graph[1][2] = 2; Graph[1][3] = 0; Graph[1][4] = 0; Graph[1][5] = 3; Graph[1][6] = 0; Graph[2][0] = 1; Graph[2][1] = 2; Graph[2][2] = 0; Graph[2][3] = 1; Graph[2][4] = 3; Graph[2][5] = 0; Graph[2][6] = 0; Graph[3][0] = 2; Graph[3][1] = 0; Graph[3][2] = 1; Graph[3][3] = 0; Graph[3][4] = 0; Graph[3][5] = 0; Graph[3][6] = 1; Graph[4][0] = 0; Graph[4][1] = 0; Graph[4][2] = 3; Graph[4][3] = 0; Graph[4][4] = 0; Graph[4][5] = 2; Graph[4][6] = 0; Graph[5][0] = 0; Graph[5][1] = 3; Graph[5][2] = 0; Graph[5][3] = 0; Graph[5][4] = 2; Graph[5][5] = 0; Graph[5][6] = 1; Graph[6][0] = 0; Graph[6][1] = 0; Graph[6][2] = 0; Graph[6][3] = 1; Graph[6][4] = 0; Graph[6][5] = 1; Graph[6][6] = 0; u = 0; Dijkstra(Graph, n, u); return 0; } ``` ```cpp // Dijkstra's Algorithm in C++ #include <iostream> #include <vector> #define INT_MAX 10000000 using namespace std; void DijkstrasTest(); int main() { DijkstrasTest(); return 0; } class Node; class Edge; void Dijkstras(); vector<Node*>* AdjacentRemainingNodes(Node* node); Node* ExtractSmallest(vector<Node*>& nodes); int Distance(Node* node1, Node* node2); bool Contains(vector<Node*>& nodes, Node* node); void PrintShortestRouteTo(Node* destination); vector<Node*> nodes; vector<Edge*> edges; class Node { public: Node(char id) : id(id), previous(NULL), distanceFromStart(INT_MAX) { nodes.push_back(this); } public: char id; Node* previous; int distanceFromStart; }; class Edge { public: Edge(Node* node1, Node* node2, int distance) : node1(node1), node2(node2), distance(distance) { edges.push_back(this); } bool Connects(Node* node1, Node* node2) { return ( (node1 == this->node1 && node2 == this->node2) || (node1 == this->node2 && node2 == this->node1)); } public: Node* node1; Node* node2; int distance; }; /////////////////// void DijkstrasTest() { Node* a = new Node('a'); Node* b = new Node('b'); Node* c = new Node('c'); Node* d = new Node('d'); Node* e = new Node('e'); Node* f = new Node('f'); Node* g = new Node('g'); Edge* e1 = new Edge(a, c, 1); Edge* e2 = new Edge(a, d, 2); Edge* e3 = new Edge(b, c, 2); Edge* e4 = new Edge(c, d, 1); Edge* e5 = new Edge(b, f, 3); Edge* e6 = new Edge(c, e, 3); Edge* e7 = new Edge(e, f, 2); Edge* e8 = new Edge(d, g, 1); Edge* e9 = new Edge(g, f, 1); a->distanceFromStart = 0; // set start node Dijkstras(); PrintShortestRouteTo(f); } /////////////////// void Dijkstras() { while (nodes.size() > 0) { Node* smallest = ExtractSmallest(nodes); vector<Node*>* adjacentNodes = AdjacentRemainingNodes(smallest); const int size = adjacentNodes->size(); for (int i = 0; i < size; ++i) { Node* adjacent = adjacentNodes->at(i); int distance = Distance(smallest, adjacent) + smallest->distanceFromStart; if (distance < adjacent->distanceFromStart) { adjacent->distanceFromStart = distance; adjacent->previous = smallest; } } delete adjacentNodes; } } // Find the node with the smallest distance, // remove it, and return it. Node* ExtractSmallest(vector<Node*>& nodes) { int size = nodes.size(); if (size == 0) return NULL; int smallestPosition = 0; Node* smallest = nodes.at(0); for (int i = 1; i < size; ++i) { Node* current = nodes.at(i); if (current->distanceFromStart < smallest->distanceFromStart) { smallest = current; smallestPosition = i; } } nodes.erase(nodes.begin() + smallestPosition); return smallest; } // Return all nodes adjacent to 'node' which are still // in the 'nodes' collection. vector<Node*>* AdjacentRemainingNodes(Node* node) { vector<Node*>* adjacentNodes = new vector<Node*>(); const int size = edges.size(); for (int i = 0; i < size; ++i) { Edge* edge = edges.at(i); Node* adjacent = NULL; if (edge->node1 == node) { adjacent = edge->node2; } else if (edge->node2 == node) { adjacent = edge->node1; } if (adjacent && Contains(nodes, adjacent)) { adjacentNodes->push_back(adjacent); } } return adjacentNodes; } // Return distance between two connected nodes int Distance(Node* node1, Node* node2) { const int size = edges.size(); for (int i = 0; i < size; ++i) { Edge* edge = edges.at(i); if (edge->Connects(node1, node2)) { return edge->distance; } } return -1; // should never happen } // Does the 'nodes' vector contain 'node' bool Contains(vector<Node*>& nodes, Node* node) { const int size = nodes.size(); for (int i = 0; i < size; ++i) { if (node == nodes.at(i)) { return true; } } return false; } /////////////////// void PrintShortestRouteTo(Node* destination) { Node* previous = destination; cout << "Distance from start: " << destination->distanceFromStart << endl; while (previous) { cout << previous->id << " "; previous = previous->previous; } cout << endl; } // these two not needed vector<Edge*>* AdjacentEdges(vector<Edge*>& Edges, Node* node); void RemoveEdge(vector<Edge*>& Edges, Edge* edge); vector<Edge*>* AdjacentEdges(vector<Edge*>& edges, Node* node) { vector<Edge*>* adjacentEdges = new vector<Edge*>(); const int size = edges.size(); for (int i = 0; i < size; ++i) { Edge* edge = edges.at(i); if (edge->node1 == node) { cout << "adjacent: " << edge->node2->id << endl; adjacentEdges->push_back(edge); } else if (edge->node2 == node) { cout << "adjacent: " << edge->node1->id << endl; adjacentEdges->push_back(edge); } } return adjacentEdges; } void RemoveEdge(vector<Edge*>& edges, Edge* edge) { vector<Edge*>::iterator it; for (it = edges.begin(); it < edges.end(); ++it) { if (*it == edge) { edges.erase(it); return; } } } ``` * * * ## Dijkstra 算法復雜度時間復雜度：`O(E Log V)` 其中，`E`是邊數，`V`是頂點數。空間復雜度：`O(V)` * * * ## Dijkstra 算法應用 * 尋找最短路徑 * 社交網絡中的應用 * 在電話網中 * 在地圖上查找位置