013贪婪算法-1.ppt

山东大学计算机科学与技术学院 数据结构 第13章 贪婪算法 * Dijkstra算法 Dijkstra(迪克斯特拉/迪杰斯特拉) 利用E. Dijkstra发明的贪婪算法可以解决最短路径问题，它通过分步方法求出最短路径。每一步产生一个到达新的目的顶点的最短路径。 Dijkstra的方法按路径长度递增顺序产生最短路径。 首先最初产生从s到它自身的路径，这条路径没有边，其长度为0。 在贪婪算法的每一步中，产生下一个最短路径。 在目前产生的每一条最短路径中，考虑加入一条最短的边，再从所有这些新路径中先选择最短的，这种策略即是Dijkstra算法。 * * * * 单源最短路问题 每一条路径(第1条除外)都是由一条已产生的最短路径加上一条边形成。 下一条最短路径总是由已产生的最短路径再扩充一条最短的边得到的，且这条路径所到达的顶点其最短路径还未产生。 * 单源最短路径 定义d[i]为在当前已产生的最短路径中加入一条最短边的最短长度，从而使得扩充的路径到达顶点i。 最初，仅有从s到s的一条长度为0的路径，这时对于每个顶点i，d[i]等于a[s][i](a是有向图的长度邻接矩阵)。 当获得一条新的最短路径后，由于新的最短路径可能会产生更小的d值，因此有些顶点的d值可能会发生变化。 在路径可到达顶点且未产生最短路径的顶点中，d()值最小的即为下一条最短路径的终点。 山东大学计算机科学与技术学院 数据结构 第13章 贪婪算法 * 单源最短路径 利用数组p来存储最短路径。 p(i) (predecessor(i))——从s到达i的路径中顶点i前面的那个顶点。 如p[1:5]=[0,1,1,3,4] p[i]=4,p[4]=3,p[3]=1=s 设路径可到达顶点且未产生最短路径的顶点列表L。 当L不空时，重复： 在L 中选择d() 值最小的顶点v ，并将顶点v 从L 中删除。 更新邻接自顶点v 的顶点的 d()值和 p()值。 山东大学计算机科学与技术学院 数据结构 第13章 贪婪算法 * Dijkstra算法 1) 初始化d[i]=a[s][i](1≤i≤n)， 对于邻接于s的所有顶点i，置p[i]=s, 对于其余的顶点 置p[i] = 0； 对于p[i]≠0的所有顶点建立L表。 2) 若L为空，终止，否则转至3 )。 3) 从L中删除d值最小的顶点i。 4) 对于与i邻接的所有还未到达的顶点j，更新d[j]值为min{d[j], d[i] +a[i][j]}；若d[j]发生了变化且j 还未在L中，则置p[j] = i，并将j 加入L，转至2。 山东大学计算机科学与技术学院 数据结构 第13章 贪婪算法 * 数据结构的选择 d() : 1维数组 p() : 1维数组. L:无序链表或最小堆 . 选择采用无序链表 chain * templateclass T void AdjacencyWDigraphT::ShortestPaths(int s, T d[], int p[]) {// 寻找从顶点s出发的最短路径, 在d中返回最短距离 // 在p中返回前继顶点 if (s 1 || s n) throw OutOfBounds(); Chainint L; // 路径可到达顶点的列表 ChainIteratorint I; // 初始化d, p, L for (int i = 1; i = n; i++){ d[i] = a[s][i]; if (d[i] == NoEdge) p[i] = 0; else {p[i] = s; L.Insert(0,i); } } 山东大学计算机科学与技术学院 数据结构 第13章 贪婪算法 * // 更新d, p while (!L.IsEmpty()) { // 寻找具有最小d的顶点v int *v = I.Initialize(L); int *w = I.Next(); while (w) { If (d[*w] d[*v]) v = w; w = I.Next();} // 从L中删除通向顶点v的下一最短路径并更新d int i = *v; L . Delete ( * v ) ; for (int j = 1; j = n; j++) { if (a[i][j] !