给定一个图和图中的源顶点，找出从源到给定图中所有顶点的最短路径。 Dijkstra的算法与 最小生成树的Prim算法 .就像Prim的MST一样，我们生成 SPT（最短路径树） 以给定的源作为根。我们维护两个集合，一个集合包含最短路径树中包含的顶点，另一个集合包含最短路径树中尚未包含的顶点。在算法的每一步，我们都会找到另一个集合（尚未包含的集合）中的顶点，该顶点与源之间的距离最小。 下面是Dijkstra算法中使用的详细步骤，用于寻找从单个源顶点到给定图形中所有其他顶点的最短路径。
null
算法 1) 创建一个集合 间谍网 （最短路径树集）跟踪最短路径树中包含的顶点，即计算并最终确定其与源的最小距离。最初，这个集合是空的。 2) 为输入图形中的所有顶点指定一个距离值。将所有距离值初始化为无限。将源顶点的“距离”值指定为0，以便首先拾取该顶点。 3) 虽然 间谍网 不包括所有顶点 …. （a） 选择一个顶点u，它不在图中 间谍网 并且具有最小距离值。 …. b） 包括你到 间谍网 . …. c） 更新u的所有相邻顶点的距离值。要更新距离值，请遍历所有相邻顶点。对于每个相邻顶点v，如果u（从源）的距离值和边u-v的权重之和小于v的距离值，则更新v的距离值。
让我们用下面的例子来理解：
![图片[1]-Dijkstra最短路径算法|贪婪算法-7-yiteyi-C++库](https://www.geeksforgeeks.org/wp-content/uploads/Fig-11.jpg)
布景 间谍网 最初为空，分配给顶点的距离为{0，INF，INF，INF，INF，INF，INF}，其中INF表示无限。现在用最小距离值拾取顶点。将拾取顶点0，并将其包含在 间谍网 所以 间谍网 变成{0}。包括0到 间谍网 ，更新其相邻顶点的距离值。0的相邻顶点是1和7。距离值1和7将更新为4和8。下面的子图显示顶点及其距离值，仅显示具有有限距离值的顶点。SPT中包含的顶点以绿色显示。
![图片[2]-Dijkstra最短路径算法|贪婪算法-7-yiteyi-C++库](https://www.geeksforgeeks.org/wp-content/uploads/MST1.jpg)
拾取具有最小距离值且尚未包含在SPT（未包含在sptSET）中的顶点。将拾取顶点1并将其添加到sptSet。所以sptSet现在变成了{0，1}。更新1的相邻顶点的距离值。顶点2的距离值变为12。
![图片[3]-Dijkstra最短路径算法|贪婪算法-7-yiteyi-C++库](https://www.geeksforgeeks.org/wp-content/uploads/DIJ2.jpg)
拾取具有最小距离值且尚未包含在SPT（未包含在sptSET）中的顶点。顶点7已拾取。所以sptSet现在变成了{0,1,7}。更新7的相邻顶点的距离值。顶点6和8的距离值变得有限（分别为15和9）。
![图片[4]-Dijkstra最短路径算法|贪婪算法-7-yiteyi-C++库](https://www.geeksforgeeks.org/wp-content/uploads/DIJ3.jpg)
拾取具有最小距离值且尚未包含在SPT（未包含在sptSET）中的顶点。顶点6已拾取。所以sptSet现在变成了{0,1,7,6}。更新6的相邻顶点的距离值。顶点5和8的距离值将更新。
![图片[5]-Dijkstra最短路径算法|贪婪算法-7-yiteyi-C++库](https://www.geeksforgeeks.org/wp-content/uploads/DIJ4.jpg)
我们重复上述步骤，直到 间谍网 包括给定图形的所有顶点。最后，我们得到以下最短路径树（SPT）。
![图片[6]-Dijkstra最短路径算法|贪婪算法-7-yiteyi-C++库](https://www.geeksforgeeks.org/wp-content/uploads/DIJ5.jpg)
如何实现上述算法？
我们使用一个布尔数组sptSet[]来表示SPT中包含的顶点集。如果值sptSet[v]为真，则顶点v包括在SPT中，否则不包括在内。Array dist[]用于存储所有顶点的最短距离值。
C++
// A C++ program for Dijkstra's single source shortest path algorithm. // The program is for adjacency matrix representation of the graph #include <iostream> using namespace std; #include <limits.h> // Number of vertices in the graph #define V 9 // A utility function to find the vertex with minimum distance value, from // the set of vertices not yet included in shortest path tree int minDistance( int dist[], bool sptSet[]) { // Initialize min value int min = INT_MAX, min_index; for ( int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } // A utility function to print the constructed distance array void printSolution( int dist[]) { cout << "Vertex Distance from Source" << endl; for ( int i = 0; i < V; i++) cout << i << " " <<dist[i]<< endl; } // Function that implements Dijkstra's single source shortest path algorithm // for a graph represented using adjacency matrix representation void dijkstra( int graph[V][V], int src) { int dist[V]; // The output array. dist[i] will hold the shortest // distance from src to i bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest // path tree or shortest distance from src to i is finalized // Initialize all distances as INFINITE and stpSet[] as false for ( int i = 0; i < V; i++) dist[i] = INT_MAX, sptSet[i] = false ; // Distance of source vertex from itself is always 0 dist[src] = 0; // Find shortest path for all vertices for ( int count = 0; count < V - 1; count++) { // Pick the minimum distance vertex from the set of vertices not // yet processed. u is always equal to src in the first iteration. int u = minDistance(dist, sptSet); // Mark the picked vertex as processed sptSet[u] = true ; // Update dist value of the adjacent vertices of the picked vertex. for ( int v = 0; v < V; v++) // Update dist[v] only if is not in sptSet, there is an edge from // u to v, and total weight of path from src to v through u is // smaller than current value of dist[v] if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; } // print the constructed distance array printSolution(dist); } // driver program to test above function int main() { /* Let us create the example graph discussed above */ int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, { 0, 0, 2, 0, 0, 0, 6, 7, 0 } }; dijkstra(graph, 0); return 0; } // This code is contributed by shivanisinghss2110 |
C
// A C++ program for Dijkstra's single source shortest path algorithm. // The program is for adjacency matrix representation of the graph #include <limits.h> #include <stdio.h> #include <stdbool.h> // Number of vertices in the graph #define V 9 // A utility function to find the vertex with minimum distance value, from // the set of vertices not yet included in shortest path tree int minDistance( int dist[], bool sptSet[]) { // Initialize min value int min = INT_MAX, min_index; for ( int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } // A utility function to print the constructed distance array void printSolution( int dist[]) { printf ( "Vertex Distance from Source" ); for ( int i = 0; i < V; i++) printf ( "%d %d" , i, dist[i]); } // Function that implements Dijkstra's single source shortest path algorithm // for a graph represented using adjacency matrix representation void dijkstra( int graph[V][V], int src) { int dist[V]; // The output array. dist[i] will hold the shortest // distance from src to i bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest // path tree or shortest distance from src to i is finalized // Initialize all distances as INFINITE and stpSet[] as false for ( int i = 0; i < V; i++) dist[i] = INT_MAX, sptSet[i] = false ; // Distance of source vertex from itself is always 0 dist[src] = 0; // Find shortest path for all vertices for ( int count = 0; count < V - 1; count++) { // Pick the minimum distance vertex from the set of vertices not // yet processed. u is always equal to src in the first iteration. int u = minDistance(dist, sptSet); // Mark the picked vertex as processed sptSet[u] = true ; // Update dist value of the adjacent vertices of the picked vertex. for ( int v = 0; v < V; v++) // Update dist[v] only if is not in sptSet, there is an edge from // u to v, and total weight of path from src to v through u is // smaller than current value of dist[v] if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; } // print the constructed distance array printSolution(dist); } // driver program to test above function int main() { /* Let us create the example graph discussed above */ int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, { 0, 0, 2, 0, 0, 0, 6, 7, 0 } }; dijkstra(graph, 0); return 0; } |
JAVA
// A Java program for Dijkstra's single source shortest path algorithm. // The program is for adjacency matrix representation of the graph import java.util.*; import java.lang.*; import java.io.*; class ShortestPath { // A utility function to find the vertex with minimum distance value, // from the set of vertices not yet included in shortest path tree static final int V = 9 ; int minDistance( int dist[], Boolean sptSet[]) { // Initialize min value int min = Integer.MAX_VALUE, min_index = - 1 ; for ( int v = 0 ; v < V; v++) if (sptSet[v] == false && dist[v] <= min) { min = dist[v]; min_index = v; } return min_index; } // A utility function to print the constructed distance array void printSolution( int dist[]) { System.out.println( "Vertex Distance from Source" ); for ( int i = 0 ; i < V; i++) System.out.println(i + " " + dist[i]); } // Function that implements Dijkstra's single source shortest path // algorithm for a graph represented using adjacency matrix // representation void dijkstra( int graph[][], int src) { int dist[] = new int [V]; // The output array. dist[i] will hold // the shortest distance from src to i // sptSet[i] will true if vertex i is included in shortest // path tree or shortest distance from src to i is finalized Boolean sptSet[] = new Boolean[V]; // Initialize all distances as INFINITE and stpSet[] as false for ( int i = 0 ; i < V; i++) { dist[i] = Integer.MAX_VALUE; sptSet[i] = false ; } // Distance of source vertex from itself is always 0 dist[src] = 0 ; // Find shortest path for all vertices for ( int count = 0 ; count < V - 1 ; count++) { // Pick the minimum distance vertex from the set of vertices // not yet processed. u is always equal to src in first // iteration. int u = minDistance(dist, sptSet); // Mark the picked vertex as processed sptSet[u] = true ; // Update dist value of the adjacent vertices of the // picked vertex. for ( int v = 0 ; v < V; v++) // Update dist[v] only if is not in sptSet, there is an // edge from u to v, and total weight of path from src to // v through u is smaller than current value of dist[v] if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; } // print the constructed distance array printSolution(dist); } // Driver method public static void main(String[] args) { /* Let us create the example graph discussed above */ int graph[][] = new int [][] { { 0 , 4 , 0 , 0 , 0 , 0 , 0 , 8 , 0 }, { 4 , 0 , 8 , 0 , 0 , 0 , 0 , 11 , 0 }, { 0 , 8 , 0 , 7 , 0 , 4 , 0 , 0 , 2 }, { 0 , 0 , 7 , 0 , 9 , 14 , 0 , 0 , 0 }, { 0 , 0 , 0 , 9 , 0 , 10 , 0 , 0 , 0 }, { 0 , 0 , 4 , 14 , 10 , 0 , 2 , 0 , 0 }, { 0 , 0 , 0 , 0 , 0 , 2 , 0 , 1 , 6 }, { 8 , 11 , 0 , 0 , 0 , 0 , 1 , 0 , 7 }, { 0 , 0 , 2 , 0 , 0 , 0 , 6 , 7 , 0 } }; ShortestPath t = new ShortestPath(); t.dijkstra(graph, 0 ); } } // This code is contributed by Aakash Hasija |
python
# Python program for Dijkstra's single # source shortest path algorithm. The program is # for adjacency matrix representation of the graph # Library for INT_MAX import sys class Graph(): def __init__( self , vertices): self .V = vertices self .graph = [[ 0 for column in range (vertices)] for row in range (vertices)] def printSolution( self , dist): print ( "Vertex Distance from Source" ) for node in range ( self .V): print (node, " " , dist[node]) # A utility function to find the vertex with # minimum distance value, from the set of vertices # not yet included in shortest path tree def minDistance( self , dist, sptSet): # Initialize minimum distance for next node min = sys.maxsize # Search not nearest vertex not in the # shortest path tree for u in range ( self .V): if dist[u] < min and sptSet[u] = = False : min = dist[u] min_index = u return min_index # Function that implements Dijkstra's single source # shortest path algorithm for a graph represented # using adjacency matrix representation def dijkstra( self , src): dist = [sys.maxsize] * self .V dist[src] = 0 sptSet = [ False ] * self .V for cout in range ( self .V): # Pick the minimum distance vertex from # the set of vertices not yet processed. # x is always equal to src in first iteration x = self .minDistance(dist, sptSet) # Put the minimum distance vertex in the # shortest path tree sptSet[x] = True # Update dist value of the adjacent vertices # of the picked vertex only if the current # distance is greater than new distance and # the vertex in not in the shortest path tree for y in range ( self .V): if self .graph[x][y] > 0 and sptSet[y] = = False and dist[y] > dist[x] + self .graph[x][y]: dist[y] = dist[x] + self .graph[x][y] self .printSolution(dist) # Driver program g = Graph( 9 ) g.graph = [[ 0 , 4 , 0 , 0 , 0 , 0 , 0 , 8 , 0 ], [ 4 , 0 , 8 , 0 , 0 , 0 , 0 , 11 , 0 ], [ 0 , 8 , 0 , 7 , 0 , 4 , 0 , 0 , 2 ], [ 0 , 0 , 7 , 0 , 9 , 14 , 0 , 0 , 0 ], [ 0 , 0 , 0 , 9 , 0 , 10 , 0 , 0 , 0 ], [ 0 , 0 , 4 , 14 , 10 , 0 , 2 , 0 , 0 ], [ 0 , 0 , 0 , 0 , 0 , 2 , 0 , 1 , 6 ], [ 8 , 11 , 0 , 0 , 0 , 0 , 1 , 0 , 7 ], [ 0 , 0 , 2 , 0 , 0 , 0 , 6 , 7 , 0 ] ]; g.dijkstra( 0 ); # This code is contributed by Divyanshu Mehta and Updated by Pranav Singh Sambyal |
C#
// A C# program for Dijkstra's single // source shortest path algorithm. // The program is for adjacency matrix // representation of the graph using System; class GFG { // A utility function to find the // vertex with minimum distance // value, from the set of vertices // not yet included in shortest // path tree static int V = 9; int minDistance( int [] dist, bool [] sptSet) { // Initialize min value int min = int .MaxValue, min_index = -1; for ( int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) { min = dist[v]; min_index = v; } return min_index; } // A utility function to print // the constructed distance array void printSolution( int [] dist) { Console.Write( "Vertex Distance " + "from Source" ); for ( int i = 0; i < V; i++) Console.Write(i + " " + dist[i] + "" ); } // Function that implements Dijkstra's // single source shortest path algorithm // for a graph represented using adjacency // matrix representation void dijkstra( int [, ] graph, int src) { int [] dist = new int [V]; // The output array. dist[i] // will hold the shortest // distance from src to i // sptSet[i] will true if vertex // i is included in shortest path // tree or shortest distance from // src to i is finalized bool [] sptSet = new bool [V]; // Initialize all distances as // INFINITE and stpSet[] as false for ( int i = 0; i < V; i++) { dist[i] = int .MaxValue; sptSet[i] = false ; } // Distance of source vertex // from itself is always 0 dist[src] = 0; // Find shortest path for all vertices for ( int count = 0; count < V - 1; count++) { // Pick the minimum distance vertex // from the set of vertices not yet // processed. u is always equal to // src in first iteration. int u = minDistance(dist, sptSet); // Mark the picked vertex as processed sptSet[u] = true ; // Update dist value of the adjacent // vertices of the picked vertex. for ( int v = 0; v < V; v++) // Update dist[v] only if is not in // sptSet, there is an edge from u // to v, and total weight of path // from src to v through u is smaller // than current value of dist[v] if (!sptSet[v] && graph[u, v] != 0 && dist[u] != int .MaxValue && dist[u] + graph[u, v] < dist[v]) dist[v] = dist[u] + graph[u, v]; } // print the constructed distance array printSolution(dist); } // Driver Code public static void Main() { /* Let us create the example graph discussed above */ int [, ] graph = new int [, ] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, { 0, 0, 2, 0, 0, 0, 6, 7, 0 } }; GFG t = new GFG(); t.dijkstra(graph, 0); } } // This code is contributed by ChitraNayal |
Javascript
<script> // A Javascript program for Dijkstra's single // source shortest path algorithm. // The program is for adjacency matrix // representation of the graph let V = 9; // A utility function to find the // vertex with minimum distance // value, from the set of vertices // not yet included in shortest // path tree function minDistance(dist,sptSet) { // Initialize min value let min = Number.MAX_VALUE; let min_index = -1; for (let v = 0; v < V; v++) { if (sptSet[v] == false && dist[v] <= min) { min = dist[v]; min_index = v; } } return min_index; } // A utility function to print // the constructed distance array function printSolution(dist) { document.write( "Vertex Distance from Source<br>" ); for (let i = 0; i < V; i++) { document.write(i + " " + dist[i] + "<br>" ); } } // Function that implements Dijkstra's // single source shortest path algorithm // for a graph represented using adjacency // matrix representation function dijkstra(graph, src) { let dist = new Array(V); let sptSet = new Array(V); // Initialize all distances as // INFINITE and stpSet[] as false for (let i = 0; i < V; i++) { dist[i] = Number.MAX_VALUE; sptSet[i] = false ; } // Distance of source vertex // from itself is always 0 dist[src] = 0; // Find shortest path for all vertices for (let count = 0; count < V - 1; count++) { // Pick the minimum distance vertex // from the set of vertices not yet // processed. u is always equal to // src in first iteration. let u = minDistance(dist, sptSet); // Mark the picked vertex as processed sptSet[u] = true ; // Update dist value of the adjacent // vertices of the picked vertex. for (let v = 0; v < V; v++) { // Update dist[v] only if is not in // sptSet, there is an edge from u // to v, and total weight of path // from src to v through u is smaller // than current value of dist[v] if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Number.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) { dist[v] = dist[u] + graph[u][v]; } } } // Print the constructed distance array printSolution(dist); } // Driver code let graph = [ [ 0, 4, 0, 0, 0, 0, 0, 8, 0 ], [ 4, 0, 8, 0, 0, 0, 0, 11, 0 ], [ 0, 8, 0, 7, 0, 4, 0, 0, 2 ], [ 0, 0, 7, 0, 9, 14, 0, 0, 0], [ 0, 0, 0, 9, 0, 10, 0, 0, 0 ], [ 0, 0, 4, 14, 10, 0, 2, 0, 0], [ 0, 0, 0, 0, 0, 2, 0, 1, 6 ], [ 8, 11, 0, 0, 0, 0, 1, 0, 7 ], [ 0, 0, 2, 0, 0, 0, 6, 7, 0 ] ] dijkstra(graph, 0); // This code is contributed by rag2127 </script> |
输出：
Vertex Distance from Source0 01 42 123 194 215 116 97 88 14
笔记： 1) 该代码计算最短距离，但不计算路径信息。我们可以创建一个父数组，在距离更新时更新父数组（如 prim的实现 )并使用它显示从源到不同顶点的最短路径。 2) 该代码用于无向图，同样的Dijkstra函数也可用于有向图。 3) 该代码查找从源到所有顶点的最短距离。如果我们只对从源到单个目标的最短距离感兴趣，我们可以在拾取的最小距离顶点等于目标时打破for循环（算法的步骤3.a）。 4) 实现的时间复杂度为O（V^2）。如果输入 图用邻接表表示 在二进制堆的帮助下，它可以简化为O（E log V）。请看 邻接表表示的Dijkstra算法 更多细节。 5) Dijkstra算法不适用于具有负权圈的图。对于具有负边的图，它可能会给出正确的结果，但必须允许一个顶点可以被多次访问，该版本将失去其快速时间复杂性。对于具有负权边和负权圈的图， 贝尔曼-福特算法 可以使用，我们将很快作为一个单独的帖子进行讨论。
邻接表表示的Dijkstra算法 Dijkstra最短路径算法中的打印路径 基于STL集合的Dijkstra最短路径算法
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
