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 */ }
时间: 2024-04-27 08:25:16 浏览: 27
在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]的时候,同时判断是否需要更新最短路径。
相关问题
Use Dijkstra's algorithm to find the shortest paths from vertex a to other vertices. In which order that the results must be obtained?
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.
each node knows only the distances to its immediate neighbors. (b) each node
每个节点只知道与其直接相连的节点的距离。这种情况下,节点之间的距离信息是局部且有限的。与全局信息相比,它不能提供节点之间的完整路径信息。但是,这种局部信息仍然可以用于某些问题的解决。
首先,每个节点可以使用其直接邻居的距离信息来进行局部最短路径算法,如Dijkstra算法。节点可以根据其直接邻居的距离,选择到达目标节点的最佳下一跳节点。然后,通过重复此过程,节点可以逐步构建到达目标节点的完整路径。
此外,节点之间的局部距离信息还可以用于构建拓扑图。节点可以使用其直接邻居的距离信息来构建邻接矩阵或邻接列表。这样的拓扑图可以用于分析网络结构和性能,并且可以在某些算法中用作输入。
然而,节点之间只知道与其直接邻居的距离也存在一些限制。如果网络中存在环路或无法达到的节点,节点之间的局部距离信息可能不足以找到全局最佳路径。在这种情况下,要解决这个问题,我们可能需要引入其他信息,比如进行更广泛的信息交换,或使用分布式算法来解决问题。