图的最短路径问题.ppt

最短路径问题 输入: 每条边上标记了权(weights)或代价(costs) 的图. 输出: 组成最短路径的边的序列. 例如: 寻找两个指定顶点之间的最短路径 寻找从一个顶点S到图中所有其他顶点的最短路径 寻找所有顶点对之间的最短路径 我们介绍的算法将仅计算最短路径的长度,而不记录实际路径. 最短路径的定义 用记号d(A, B)表示从顶点 A 到 B 的最短距离. 定义w(A, B)为边(A , B)的权. 如果两点之间没有边, 那么w(A, B) = ?. 求从某个源点到其余各点的最短路径 单源最短路径 在图 G 中给定一个顶点S,找出从S到G中所有其他顶点的最短路径. Try 1: 用某种顺序访问顶点, 计算了迄今为止所有顶点的最短路径, 然后添加到下一个顶点x的最短路径. 问题: 已经处理了的顶点的最短路径中有可能经过x. 解决方案: 如果以从 s 出发所到达的距离(递增)为顺序，对各个顶点进行处理就能避免上述问题. Dijkstra’s Algorithm Example Dijkstra’s Implementation // Compute shortest path distances from s, // return them in D void Dijkstra(Graph* G, int* D, int s) { int i, v, w; for (i=0; iG.n(); i++) D[i] = INFINITY; D[s] = 0; for (i=0; iG-n(); i++) { // Do vertices v = minVertex(G, D); if (D[v] == INFINITY) return; G-setMark(v, VISITED); for (w=G-first(v); wG-n(); w = G-next(v,w)) if (D[w] (D[v] + G-weight(v, w))) D[w] = D[v] + G-weight(v, w); } } Implementing minVertex 问题: 如何决定下一个最靠近的顶点? (也就是,寻找未访问顶点最小D值 minVertex) 方法1:通过扫描整个包含|V|个元素的表来有哪些信誉好的足球投注网站最小值. Cost: Q(|V|2 + |E|) = Q(|V|2). 方法 2: 将未被处理的顶点以D值大小为顺序保存在一个用最小堆实现的优先级队列中，可以使用Θ(log|V|)次有哪些信誉好的足球投注网站找出下一个最近顶点。每次改变D(x)值时，都可以通过先删除再重新插入的方法改变顶点x在堆中的位置. Cost: Q((|V| + |E|)log|V|) Approach 1 // Find min cost vertex int minVertex(Graph* G, int* D) { int i, v; // Set v to an unvisited vertex for (i=0; iG-n(); i++) if (G-getMark(i) == UNVISITED) { v = i; break; } // Now find smallest D value for (i++; iG-n(); i++) if ((G-getMark(i) == UNVISITED) (D[i] D[v])) v = i; return v; } Approach 2 void Dijkstra(Graph* G, int* D, int s) { int i, v, w; // v is current vertex DijkElem temp; DijkElem E[G-e()]; // Heap array temp.distance = 0; temp.vertex = s; E[0] = temp; // Initialize heap array minheapDijkElem, DDComp H(E, 1, G-e()); for (i=0; iG.n(); i++) D[i] = INFINITY; D[s] = 0; for (i=0; iG-n(); i++) {// Get distances do { if(!H.removemin(temp)) return; v = temp.vertex; } while