数据结构第5单元图.pptVIP

Dijkstra算法程序实现（续1） // 用Dijkstra算法求有向图g的顶点vex到其余顶点的最短路径，返回 TableEntry类型数组 template class VertexType TableEntry* ShortestPath_DIJ(ALGraphVertexType g, VertexType vex) { int i, v, w; int start=g.LocateVertex(vex); EdgeNode* edge; TableEntry* table=new TableEntry[g.GetNumVertices()]; //init table for(i=0; ig.GetNumVertices(); i++){ table[i].known=false; table[i].dist=INT_MAX; table[i].preVertex=-1; } table[start].dist=0; Dijkstra算法程序实现（续2） while(true){ v=SmallestUnknownDistIndex(table, g.GetNumVertices()); if(v==-1) break; table[v].known=true; for(w=g.GetFirstAdjVex(v); w!=-1; w=g.GetNextAdjVex(v,w)){ if(!table[w].known){ g.GetEdge(v, w, edge); if(table[v].dist+edge-weighttable[w].dist){ table[w].dist=table[v].dist+edge-weight; table[w].preVertex=v; } } } } return table; } 5.6.2每对顶点间的最短路径 对于n个顶点的图，求每一对顶点间的最短路径，方法有二： 按Dijkstra算法，求每个顶点到其他各顶点间的最短路径，每次以一个顶点为源点，重复执行Dijkstra算法。总时间复杂度是O(n3)； 弗洛伊德（Floyd）提出来的，时间复杂度也是O(n3)，但形式上简单。 弗洛伊德算法 基本思想：从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径。 若vi,vj存在，则存在路径{vi,vj} // 路径中不含其它顶点 若vi,v1,v1,vj存在，则存在路径{vi,v1,vj} // 路径中所含顶点序号不大于1 若{vi,…,v2}, {v2,…,vj}存在，则存在一条路径{vi, …, v2, …vj} // 路径中所含顶点序号不大于2 … 依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。 弗洛伊德算法 假设Ak(i, j)表示顶点i到j的中间顶点序号不大于k的最短路径长度（k=1，2，?，n），那么对它做n次迭代，第n次迭代后，An(i, j)即为i到j的最短路径值，因为它中间的顶点不受限制，即允许为1～n。算法递推的产生个矩阵序列（逻辑上）：A1, A2,?, An 其始基是A0=g（即图的邻接矩阵）。 设图顶点是从1起编的连续自然数，每条弧i, j都有一个非负的权值cost(i, j)，弧i, j不存在时，cost(i, j)=∞；对任意不同的顶点i和j，定义Ak(i, j)为顶点i到j的中间顶点序号不大于k的最短路径长度，那么 A0(i, j)= cost(i, j) Ak(i, j)=Min{ Ak-1(i, j), Ak-1(i, k)+ Ak-1(k, j)} （k≥1） 本章小结 1. 熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。 2. 熟练掌握图的两种有哪些信誉好的足球投注网站路径的遍历：遍历的逻辑定义、深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站的算法。 在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。 3. 应用图的遍历算法求解各种简单路径问题。 4. 理解教科书中讨论的各种图的算法。 Thank You!