• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

最短路径dijkstra,floyd

算法笔记 站点默认 10个月前 (11-28) 216次浏览 已收录 1个评论
文章目录[隐藏]

最短路径分为两类,单元最短路径和多源最短路径。

单源最短路径

无权图的单源最短路径

这里我先说一下我的理解,我们求一个顶点到其它各顶点的最短路径,那么肯定得用bfs算法来遍历。之前的图的遍历和应用中,dfs用了很多,那么现在完全就是类比的概念了,在求两个顶点u,v的路径长度的时候,我们给dfs加了两个形参终点v和长度的d,那么这个bfs的算法也是类是的,不过我们得需要一个数组存储每个顶点到原点的距离,因为是遍历所有的顶点,那么形参v就可以省去了,此时我们需要带一个形参数组进去吗??其实大可不必,别忘了我们还有visited(标记数组),我们完全可以用它来存储数据,(那么标记的作用岂不是消失了?)并没有,我们初始值,设为一个一看就不是该顶点到初始顶点的距离的数,比如-1,这样当我们存储改顶点到初始顶点的值进去了,直接判断大于0即可,别忘了,我们还需要一个数组来存储路径,(岂不是需要n个数组来记录n个顶点到源点的路径)根本不用,我们只需要一个数组,数组下标对应的每个顶点中存储它上一步的顶点,即是从哪个顶点过来的,这样当我们需要输出从源点到x点的路径的时候,我们只需要输出数组下标x,对应的值就是从某个顶点过来的,如此追踪即可,这是反的路径,我们可以压入栈中,在将其输出。

有权图的单源最短路径

这个时候就有一个金光闪闪的算法了dijkstra算法
问题描述
给定一个带权有向图 G=(V,E) ,其中每条边的权是一个非负实数。另外,还给定 V 中的一个顶点,称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
Dijkstra算法的解决方案
Dijkstra提出按各顶点与源点v间的路径长度的递增次序,生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从源点v 到其它各顶点的最短路径全部求出为止。
Dijkstra算法的解题思想
将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中,S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。然后每次从T集合中选择S集合点中到T路径最短的那个点,并加入到集合S中,并把这个点从集合T删除。直到T集合为空为止。
具体步骤
1、选一顶点v为源点,并视从源点v出发的所有边为到各顶点的最短路径(确定数据结构:因为求的是最短路径,所以①就要用一个记录从源点v到其它各顶点的路径长度数组dist[],开始时,dist是源点v到顶点i的直接边长度,即dist中记录的是邻接阵的第v行。②设一个用来记录从源点到其它顶点的路径数组path[],path中存放路径上第i个顶点的前驱顶点)。
2、在上述的最短路径dist[]中选一条最短的,并将其终点(即)k加入到集合s中。
3、调整T中各顶点到源点v的最短路径。 因为当顶点k加入到集合s中后,源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。调整方法是比较dist[k]+g[k,j]与dist[j],取其中的较小者。
4、再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中,再回去到第三步,如此重复,直到集合S中的包含图G的所有顶点。

多元最短路径

floyd算法

太难了,学了好半天,这个算法实在是不想看了,,

核心思路编辑
路径矩阵
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 [3]
从图的带权邻接矩阵A=[a(i,j)] n×n开始,递归地进行n次更新,即由矩阵D(0)=A,按一个公式,构造出矩阵D(1);又用同样地公式由D(1)构造出D(2);……;最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度,称D(n)为图的距离矩阵,同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
采用松弛技术(松弛操作),对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);
状态转移方程
其状态转移方程如下: map[i,j]:=min{map[i,k]+map[k,j],map[i,j]};
map[i,j]表示i到j的最短距离,K是穷举i,j的断点,map[n,n]初值应该为0,或者按照题目意思来做。
当然,如果这条路没有通的话,还必须特殊处理,比如没有map[i,k]这条路。
算法过程编辑
1,从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。
2,对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
把图用邻接矩阵G表示出来,如果从Vi到Vj有路可达,则G[i][j]=d,d表示该路的长度;否则G[i][j]=无穷大。定义一个矩阵D用来记录所插入点的信息,D[i][j]表示从Vi到Vj需要经过的点,初始化D[i][j]=j。把各个顶点插入图中,比较插点后的距离与原来的距离,G[i][j] = min( G[i][j], G[i][k]+G[k][j] ),如果G[i][j]的值变小,则D[i][j]=k。在G中包含有两点之间最短道路的信息,而在D中则包含了最短通路径的信息。
比如,要寻找从V5到V1的路径。根据D,假如D(5,1)=3则说明从V5到V1经过V3,路径为{V5,V3,V1},如果D(5,3)=3,说明V5与V3直接相连,如果D(3,1)=1,说明V3与V1直接相连。 [4]
时间复杂度与空间复杂度编辑
时间复杂度:O(n^3);
空间复杂度:O(n^2)


个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:最短路径dijkstra,floyd
喜欢 (2)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到
(1)个小伙伴在吐槽