数据结构42-最短路径

《数据结构42-最短路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构第四十二课最短路径第三十四课最短路径本课主题：顶点之间的最短路径教学目的：顶点之间的最短路径教学重点：一个顶点到其它顶点间的最短路径及任意两顶点间的最短路径教学难点：一个顶点到其它顶点间的最短路径及任意两顶点间的最短路径授课内容：一﹑从某个源点到其它各顶点间的最短路径这里路径指两顶点间的通路，路径的长度指所有经过的边的总长。“最短路径”的问题指当两个顶点间通路多于一条时，如何找出边长总和为最短的那条。Dijkstra提出按路径长度递增的次序求最短路径的方法。1.Dijkstra求最短路径的基本思想把顶点分成两组，第一组是已确

2、定最短路径的结点的集合，第二组是尚未确定最短路径的结点的集合。按路径长度递增的次序逐个把第二组的顶点放到第一组中。设求从v1到其它各顶点间的最短路径,则在任意时刻，从v1到第一组各顶点间的最短路径都不大于从v1到第二组各顶点间的最短路径。2.Dijkstra求最短路径的步骤(1)设图以邻接矩阵arcs存储，矩阵中各元素的值为各边的权值。顶点间无边时其对应权值用无穷大表示。从顶点v1到其它各顶点间的最短路径的具体步骤如下：初始化：第一组（集合s）只含顶点v1,第二组（集合t）含有图中其余顶点。设一dist向量，其下标是各顶点，元素值是

3、顶点v1到各顶点的边的权值。若v1到某顶点无边，dist向量中的对应值为无穷大。2.Dijkstra求最短路径的步骤(2)选dist中最小的权值，将其顶点（j）加入s集合。s=s{j}修改从顶点v1到集合t(t=V-s)中各顶点的最短路径长度,如果dist[j]+arcs[j][k]

4、Dijkstra求最短路径的算法(1)voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P,ShortPathTable&D){for(v=0;v

5、++i){min=INFINITY;4.Dijkstra求最短路径的算法(2)for(w=0;w

6、径，循环n-1次，加上修改最短路径的循环，是二层循环，故时间复杂度为O(n2)。若只求从源点到某一顶点间的最短路径，和求到其余顶点间的最短路径相同，时间复杂度也是O(n2)。二﹑每一对顶点间的最短路径对于n个顶点的图，求每一对顶点间的最短路径，方法有：按Dijkstra算法，求每一个顶点到其它各顶点间的最短路径，即是在上面基础上，再加一层循环，时间复杂度是O(n3)，另一种方法是弗洛伊德（floyd）提出来的，时间复杂度也是O(n3)，但形式上简单。1、弗洛伊德（floyd）算法的基本思想设求顶点vi到vj间的最短路径，若vi到vj

7、有弧，则弧上的权值是一条路径，但未必是最短路径，要经过n-1次测试。首先将顶点v1加入，即看(vi,v1),(v1,vj)是否有路径，且比(vi,vj)低，如是，则用后两段路径代替，并称这是vi到vj中间顶点序号不大于1的最短路径。再将顶点v2加入，得到vi到vj中间顶点序号不大于2的最短路径。如此下去，直到vn加入，得到vi到vj中间顶点序号不大于n的最短路径，算法结束。2.弗洛伊德（floyd）算法的实例模拟3、弗洛伊德（floyd）算法(1)voidShortestPath_FLOYD(MGraphG,PathMatrix&P

8、[],DistanceMatrix&D){for(v=0;v