数据结构第6章图(g)解析.ppt
文本预览下载声明
路径长度: 路径长度: 回路(环):第一个顶点和最后一个顶点相同的路径。 简单路径:序列中顶点不重复出现的路径。 简单回路(简单环):除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路。 template class T MGraph::MGraph(T a[ ], int n, int e) { vertexNum=n; arcNum=e; for (i=0; ivertexNum; i++) vertex[i]=a[i]; for (i=0; ivertexNum; i++) //初始化邻接矩阵 for (j=0; jvertexNum; j++) arc[i][j]=0; for (k=0; karcNum; k++) //依次输入每一条边 { cinij; //边依附的两个顶点的序号 arc[i][j]=1; arc[j][i]=1; //置有边标志 } } for (k=0; kG.vertexNum; k++) ????????for (i=0; iG.vertexNum; i++) ???????? for (j=0; jG.vertexNum; j++) ???????? if (dist[i][k]+dist[k][j]dist[i][j]) { ???????? dist[i][j]=dist[i][k]+dist[k][j]; ???????? path[i][j]=path[i][k]+path[k][j]; } } 首先计算以下与关键活动有关的量: 基本思想:对于从vi到vj的弧,进行n次试探:首先考虑路径vi,v0,vj是否存在,如果存在,则比较vi,vj和vi,v0,vj的路径长度,取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1,依此类推,在经过n次比较后,最后求得的必是从顶点vi到顶点vj的最短路径。 Floyd算法 应用举例——最短路径 0 4 11 6 0 2 3 ∞ 0 有向网图 邻接矩阵 Floyd算法 应用举例——最短路径 a c b 3 4 6 11 2 Floyd算法 应用举例——最短路径 a c b 3 4 6 11 2 dist-1 = 0 4 11 6 0 2 3 ∞ 0 path-1 = ab ac ba bc ca 初始化 Floyd算法 应用举例——最短路径 a c b 3 4 6 11 2 dist-1 = 0 4 11 6 0 2 3 ∞ 0 path-1 = ab ac ba bc ca 第1次迭代 dist0 = 0 4 11 6 0 2 3 7 0 path0 = ab ac ba bc ca cab Floyd算法 应用举例——最短路径 a c b 3 4 6 11 2 第2次迭代 dist0 = 0 4 11 6 0 2 3 7 0 path0 = ab ac ba bc ca cab dist1 = 0 4 6 6 0 2 3 7 0 path1 = ab abc ba bc ca cab Floyd算法 应用举例——最短路径 a c b 3 4 6 11 2 第3次迭代 dist2 = 0 4 6 5 0 2 3 7 0 path2 = ab abc bca bc ca cab dist1 = 0 4 6 6 0 2 3 7 0 path1 = ab abc ba bc ca cab 图的存储结构:带权的邻接矩阵存储结构 数组dist[n][n]:
显示全部