数据结构课件1-11全书讲第7讲图幻灯片.ppt

这里描述的是从节点1开始到各点的dijkstra算法，其中Wa-b表示a-b的边的权值，d(i)即为最短路径值) 　1． 置集合S={2,3,...n}, 数组d(1)=0, d(i)=W1-i(1,i之间存在边) or +无穷大(1.i之间不存在边) 　2． 在S中，令d(j)=min{d(i),i属于S}，令S=S-{j}，若S为空集则算法结束，否则转3 　3． 对全部i属于S,如果存在边j-i，那么置d(i)=min{d(i), d(j)+Wj-i}，转2 　　 Dijkstra算法思想为： 设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将 加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。 算法具体步骤　 1）初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，U中顶点u距离v为边上的权（若v与u有边）或 u不是v的出边邻接点。 2）从U中选取一个距离v最小的顶点k，把k加入S中（该选定的距离就是v到k的最短路径长度）。 3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u属于 U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。 4）重复步骤（2）和（3）直到所有顶点都包含在S中。 依最短路径的长度递增的次序求得各条路径 源点 v1 … 其中，从源点到顶点v1的最短路径是所有最短路径中长度最短者 v2 在这条路径上，必定只含一条弧，并且这条弧的权值最小。 下一条路径长度次短(第1次)的最短路径的特点： 路径长度最短(第0次)的最短路径的特点： 它只可能有两种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。 其余最短路径(第k次)的特点： 再下一条路径长度次短(第2次)的最短路径的特点: 它可能有两种情况：或者是从源点不经过v2到该点； 或者是从源点到顶点v2，再到达该顶点。 它或者是从源点不经过vk到该点； 或者是从源点到vk，再到达该顶点。 求每一对顶点之间的最短路径 弗洛伊德算法的基本思想是： 从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径 顶点集为V={v1, v2,... vn} 第0步:若vi,vj存在,则存在路径{vi,vj} ，路径中不含其它顶点,相当于中间点集U={} A0[i][j]=G.arcs[i][j] (编程序时不写上标，即为A[i][j]=G.arcs[i][j]) 第1步:若vi,v1,v1,vj存在，则存在路径{vi,v1,vj} ，路径中所含顶点序号不大于1, 相当于中间点集U={v1} A1[i][j]=MIN{A0[i][j], A0[i][1]+A0[1][j]} 第2步:若{vi,…,v2}, {v2,…,vj}存在，则存在一条路径{vi, …, v2, …vj}， 路径所含顶点序号不大于2号,相当于中间点集U={v1,v2} A2[i][j]=MIN{A1[i][j], A1[i][2]+A1[2][j]} … 第n步:若{vi,…,vn}, {vn,…,vj}存在，则存在一条路径{vi, …, vn, …vj}， 路径顶点序号不大于n号, 相当于中间点集U=V,为最短路径 An[i][j]=MIN{An-1[i][j], An-1[i][n]+An-1[n][j]} template class ElemType, class WeightType void ShortestPathFloyd( const AdjListDirNetworkElemType, WeightType net, int **path, WeightType **dist) // 操作结果: 用Floyd算法求有向网net中各对顶点u和v之 // 间的最短路径path[u][v]和路径长度 // dist[u][v],path[u][v]存储从u到v的最短路径上至此 // 顶点的前一顶点的顶点号,dist[u][v]存储从u到