图详解第六篇:多源最短路径 |
您所在的位置:网站首页 › 初中语文成语运用解题技巧 › 图详解第六篇:多源最短路径 |
文章目录
多源最短路径--Floyd-Warshall算法1. 算法思想2. dist数组和pPath数组的变化3. 代码实现4. 测试观察5. 源码
前面的两篇文章我们学习了两个求解单源最短路径的算法——Dijkstra算法和Bellman-Ford算法
这两个算法都是用来求解图的单源最短路径的算法,区别在于Dijkstra算法不能求解带负权路径的图,而Bellman-Ford算法可以求解带负权路径的图,当然如果图中存在负权回路(负权环)的情况,种情况是求不出最短路径的!Bellman-Ford算法也无能为力,不过我们可以对负权回路的情况进行判定。 那这篇文章我们要再来学习一个求解多源最短路径的算法——Floyd-Warshall算法 那在前面介绍最短路径的问题的时候就已经给大家解释了什么是单源最短路径,什么是多源最短路径,我们再来回顾一下: 单源最短路径指的是从一个源节点出发,计算到其他所有节点的最短路径。也就是说,在单源最短路径问题中,只需要确定一个起点,然后计算该起点到图中所有其他节点的最短距离。 多源最短路径则是在图中计算任意两个节点之间的最短路径。换言之,需要求解所有可能的起点和终点之间的最短路径。 多源最短路径–Floyd-Warshall算法Floyd-Warshall算法是一种解决多源最短路径问题(任意两点间的最短路径)的算法。 Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法(可以求解带负权的图)。 该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 当然: 我们前面学的Dijkstra算法和Bellman-Ford算法,它们是用来求单源最短路径的,但是我们如果以所有的顶点为起点都走一遍Dijkstra/Bellman-Ford算法的话,其实也可以得到任意两点间的最短距离。 不过呢,Dijkstra算法的话不可以求解带负权路径的图,而Bellman-Ford算法呢效率又有点低。 1. 算法思想Floyd算法考虑的是一条最短路径的中间节点: 设k是最短路径p的一个中间节点,那么从i到j的最短路径p就被分成i到k和k到j的两段最短路径p1,p2。 p1是从i到k且中间节点属于{1,2,…,k-1}取得的一条最短路径;p2是从k到j且中间节点属于{1,2,…,k-1}取得的一条最短路径 那它这里如何去求i到j(i,j都可以是任意顶点)最短路径p呢?
给大家简单解释一下上面原理中的这个公式,在动态规划中应该叫状态转移方程: Di,j,k表示从i到j的最短路径,该路径经过的中间结点是剩余的结点组成的集合中的结点,假设经过k个结点,编号为1…k,然后这里就分为了两种情况: 如果路径经过了结点k,那么ij的距离就等于ik的距离加上kj的距离,然后剩余就经过k-1个点如果不经过结点k,那ij的距离就等于i到j经过k-1个点(不包括k)的距离![]() ![]() 然后呢在Floyd-Warshall算法中,记录最短路径距离(权值)的dist数组和记录路径(该路径经过了哪些点)的pPath数组我们就要做一些变化了: 前面的两个算法中我们的dist数组和pPath数组都是用了一个一维数组就行了。 但是Floyd-Warshall算法就不一样了,因为前两个算法算的是单源最短路径,而Floyd-Warshall算法是多源最短路径。 因为前面我们都是一个起点,然后求其它顶点到起点的最短路径;而现在是多源,即每个顶点都可以是起点,所以我们要记录每个顶点作为起点时到其它顶点的最短路径距离和路径。 那我们就需要用二维数组了。 3. 代码实现那下面我们就来尝试写一写Floyd-Warshall算法的代码:
🆗,搞定! 4. 测试观察那下面我们再加一个打印权值和路径的二维数组的代码,因为上面那个例子也是把每一步对应的两个二维数组(矩阵)画了出来,我们可以打印(每个顶点作为中间结点更新之后的都打印一下)出来观察对比一下:
然后我们来测试一下:
我可以给大家调整一下:
那然后呢我们可以把所有任意两点的最短路径打印一下:
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |