数据结构与算法—路径算法

《数据结构与算法—路径算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十九讲最短路径(对应教材7·6p186—P192)7·6最短路径网络中的常见问题：两点间是否有通路，哪条路径最短。本书讨论两类问题：一类是从一个顶点到其它顶点间的最短路径，另一类是任意两顶点间的最短路径。这都是有向图的应用。7·6·1从某个源点到其它各顶点间的最短路径这里路径指两顶点间的通路，路径的长度指所有经过的边的总长。“最短路径”的问题指当两个顶点间通路多于一条时，如何找出边长总和为最短的那条。Dijkstra提出按路径长度递增的次序求最短路径的方法。1、Dijkstra求最短路径的基本思想把顶点分成两组，第一组是已确定最短路

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

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

4、0¥30100v0v2v1v3v4v5¥06030100v0v2v4v1v3v5¥050090v0v2v4v3v1¥00090v0v2v4v3v5v1¥0000v0v2v4v3v5v1000001、Dijkstra求最短路径的算法voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P,ShortPathTable&D){for(v=0;v

5、FALSE;if(D[v]

6、[w];P[w]=P[v];P[w][w]=TRUE;}}}1、Dijkstra求最短路径的算法分析对于n个顶点的图，求一个顶点到其余顶点的最短路径，循环n-1次，加上修改最短路径的循环，是二层循环，故时间复杂度为O(n2)。若只求从源点到某一顶点间的最短路径，和求到其余顶点间的最短路径相同，时间复杂度也是O(n2)。6·4·2每一对顶点间的最短路径对于n个顶点的图，求每一对顶点间的最短路径，方法有二：一是按Dijkstra算法，求每一个顶点到其它各顶点间的最短路径，即是在上面基础上，再加一层循环，时间复杂度是O(n3)，另一种方法是

7、弗洛伊德（floyd）提出来的，时间复杂度也是O(n3)，但形式上简单。1、弗洛伊德（floyd）算法的基本思想设求顶点vi到vj间的最短路径，若vi到vj有弧，则弧上的权值是一条路径，但未必是最短路径，要经过n-1次测试。首先将顶点v1加入，即看(vi,v1),(v1,vj)是否有路径，且比(vi,vj)低，如是，则用后两段路径代替，并称这是vi到vj中间顶点序号不大于1的最短路径。再将顶点v2加入，得到vi到vj中间顶点序号不大于2的最短路径。如此下去，直到vn加入，得到vi到vj中间顶点序号不大于n的最短路径，算法结束。2、弗洛

8、伊德（floyd）算法的实例模拟3、弗洛伊德（floyd）算法voidShortestPath_FLOYD(MGraphG,PathMatrix&P[],DistanceMatrix&D){for(v=0;v