Use Dijkstra's algorithm to find the shortest paths from vertex a to other vertices. In which order that the results must be obtained?
时间: 2024-05-22 16:15:06 浏览: 10
The order of the results obtained from using Dijkstra's algorithm to find the shortest paths from vertex a to other vertices is not specified by the algorithm itself. However, typically the results are obtained in ascending order based on the distance from vertex a to each of the other vertices.
相关问题
设计以下问题算法:All-pairs shortest paths. The adjacency matrix is as same as that of problem 3.(Use Floyd or Johnson’s algorithm)
这是一个经典的全源最短路径问题,可以使用 Floyd 算法或者 Johnson 算法进行求解。下面给出两种算法的伪代码:
Floyd 算法:
1. 初始化一个二维数组 dist,表示任意两点之间的最短距离。将 dist[i][j] 的初始值设为 i 到 j 的距离,如果 i 和 j 不相邻,则距离设为无穷大。
2. 重复执行以下操作 V 次(V 是点的个数):
3. 对于每一对顶点 i 和 j,如果从源点 A 到 k 再到 j 的距离比直接从源点 A 到 j 的距离更短,则更新 dist[i][j] 的值为更小的距离。
4. 返回 dist 数组,其中 dist[i][j] 表示从点 i 到点 j 的最短路径长度。
Johnson 算法:
1. 对原图进行一次变换,使得图中不存在负权边。具体地,对每个点 u,添加一条边 (s,u),边权为0,其中 s 是一个新的源点。然后运用 Bellman-Ford 算法求出从 s 出发到达每个点的最短距离 h[u]。
2. 对原图进行 V 次 Dijkstra 算法,分别以每个点为源点求出该点到其他所有点的最短距离。在求解时,边权为 w(u,v)+h[u]-h[v],其中 h[u] 和 h[v] 是上一步求出的值。
3. 对于任意一对顶点 i 和 j,它们之间的最短路径长度为 dist[i][j]=dist'[i][j]+h[j]-h[i],其中 dist'[i][j] 是第二步求出的值,h[i] 和 h[j] 是第一步求出的值。
4. 返回 dist 数组,其中 dist[i][j] 表示从点 i 到点 j 的最短路径长度。
The function Dijkstra is to find the shortest path from Vertex S to every other vertices in a given Graph. The distances are stored in dist[], and path[] records the paths. The MGraph is defined as the following: typedef struct GNode *PtrToGNode; struct GNode{ int Nv; /* Number of vertices */ int Ne; /* Number of edges */ WeightType G[MaxVertexNum][MaxVertexNum]; /* adjacency matrix */ }; typedef PtrToGNode MGraph; void Dijkstra( MGraph Graph, int dist[], int path[], Vertex S ) { int collected[MaxVertexNum]; Vertex V, W; for ( V=0; V<Graph->Nv; V++ ) { dist[V] = Graph->G[S][V]; path[V] = -1; collected[V] = false; } dist[S] = 0; collected[S] = true; while (1) { V = FindMinDist( Graph, dist, collected ); if ( V==ERROR ) break; collected[V] = true; for( W=0; W<Graph->Nv; W++ ) if ( collected[W]==false && Graph->G[V][W]<INFINITY ) { if ( ) { dist[W] = ; path[W] = ; } } } /* end while */ }
在Dijkstra函数中,缺少一个条件判断语句,用来判断当前节点W是否可以通过V到达S的距离更短。应该在if语句中加上这个条件判断,如下所示:
if ( collected[W]==false && Graph->G[V][W]<INFINITY ) {
if ( dist[V] + Graph->G[V][W] < dist[W] ) {
dist[W] = dist[V] + Graph->G[V][W];
path[W] = V;
}
}
这样就可以在更新dist[W]和path[W]的时候,同时判断是否需要更新最短路径。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![none](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)