数据结构——C++实现 缪淮扣 顾训穰 沈俊 数据结构-第七章新.pptVIP

用顶点表示活动的网络 for ( i = 0; i n-1; i++ ) min = MAXNUM; u = v; for ( int j = 0; j n; j++ ) if ( !s[j] dist[j] min ) { u = j; min = dist[j]; } s[u] = 1; //将顶点u加入集合S for ( int w = 0; w n; w++ ) //修改dist和path if ( !s[w] dist[u] + Arcs[u][w] dist[w] ) { dist[w] = dist[u] + Arcs [u][w]; path[w] = u; } } } 弧上权值为任意值的单源点最短路径问题 在上一节中讨论了弧上权值为非负值的情况，接下来讨论更一般的情况，假设带权有向图G上弧的权值可能为负值。 例如，对于右图所示的带权有向图来说，利用上节给出的迪克斯特拉算法，不一定能得到正确的结果。 为了能够求解弧上带有负权值的单源最短路径问题，贝尔曼（BelLnam）和福特（Ford）提出了从源点逐次经过其它顶点，以缩短到达终点的最短路径长度的方法。该方法有一个限制条件，即要求图中不能有路径长度为负值的回路。 当图中没有路径长度为负值的回路时，有n个顶点的图中任意两个顶点之间如果存在最短路径，此路径最多有n-1条弧。 在贝尔曼—福特算法中，构造一个最短路径长度的数组序列：dist1[]、dist2[]、…、distn-1[]。 其中，dist1[u]表示从源点v0直接到终点u的最短路径的长度，即dist1[u]＝Arcs[v0][u]； 而dist2[u]表示从源点v0出发最多经过两条弧（一个中间顶点）到达终点u的最短路径的长度，…， distk[u]是从源点v0出发最多经过不构成带负长度回路的k条弧（k-1个中间顶点）到达终点u的最短路径的长度。算法的结果就是计算出distn-1[u]。 广度优先遍历的算法： templateclass vertexType, class arcTypevoid Graph vertexType, arcType :: BFTraverse (void visit( vertexType v )) { int i, n = NumberOfVertexes() ;//取图的顶点个数 int * visited = new int [n]; //定义访问标记数组 visited for ( i = 0; i n; i++ ) visited [i] = 0; //访问标记数组 visited 初始化 for ( i = 0; i n; i++ ) //对图中的每一个顶点进行判断 if (!visited [i]) BFS (i, visited, visit); delete [ ] visited; //释放 visited } templateclass vertexType, class arcType void Graph vertexType, arcType :: BFS (const int v, int visited [ ], void visit( vertexType v )) { linkqueue int q; //定义队列q visit( GetValue (v)); //访问顶点 v visited[v] = 1; //顶点 v 作已访问标记 q.EnQueue (v); //顶点 v 进队列q while ( !q.IsEmpty ( ) ) { v = q.DeQueue ( ); //否则, 队头元素出队列 int w = GetFirstNeighbor (v); while ( w != -1 ) { //若邻接顶点 w 存在 if ( !visited[w] ) { //若该邻接顶点未访问过 visit( GetValue (w)); //访问顶点 w