Floyd算法求解最短路径

这篇具有很好参考价值的文章主要介绍了Floyd算法求解最短路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1、算法概述

  Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德。

  核心思路:通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

  算法过程:

  • 从任意一条单边路径开始。左右两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。

  • 对于每一对顶点u和v,看是否存在一个顶点w使得从u到w再到v比已知的路径更短,如果更短,则更新它。

    上述概念来源于百度百科

2、算法实例

  如下图所示,我们看怎么来求解两点之间的最短路径。

Floyd算法求解最短路径

  如果要让任意两点之间(假设是a到b)的路程变短,智能引入第三个点(假设为k),并通过这个点k进行中转即a->k->b,才可能缩短为原来从顶点a到顶点b的路程。有时候可能不止一个中转点,而是经过两个或者更多的点进行中转会更短。比如上图中的4号和3号之间的路程本来是a[4][3]=12,如果通过1号中转4->1->3,路程将缩短为e[4][1]+e[1][3]=5+6=11。如果同时通过1号和2号中转的话,从4号到3号的路程会进一步缩短为e[4]+e[1][2]+e[2][3]=5+2+3=10。通过以上分析,我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。下面我们模拟该过程。

  我们使用邻接矩阵(二维数组)存储这个图,我们约定自己到自己的路程为0,1号和2号城市的路程为2,则设e[1][2]=2。2号城市无法到达4号城市,设e[2][4]=无穷大我们根据图中的权值得出如下矩阵:

Floyd算法求解最短路径

  假设我们现在只允许经过1号顶点中转,求任意两点之间的最短路径。

//经过1号顶点中转
for (int i = 1; i <=N ; i++) {
    for (int j = 1; j <=N; j++) {
        if(e[i][j]>e[i][1]+e[1][j]){
            e[i][j]=e[i][1]+e[1][j];
        }
    }
}

  此时我们只需要判断e[i][1]+e[1][j]是否比e[i][j]小就行,若小于,更新矩阵。

  由于 e [ 3 ] [ 1 ] + e [ 1 ] [ 2 ] = 7 + 2 = 9 < e [ 3 ] [ 2 ] = ∞ e[3][1]+e[1][2]=7+2=9<e[3][2]=\infty e[3][1]+e[1][2]=7+2=9<e[3][2]=,所以更新矩阵e[3][2]=9

  由于 e [ 4 ] [ 1 ] + e [ 1 ] [ 2 ] = 5 + 2 = 7 < e [ 4 ] [ 2 ] = ∞ e[4][1]+e[1][2]=5+2=7<e[4][2]=\infty e[4][1]+e[1][2]=5+2=7<e[4][2]=,所以更新矩阵e[4][2]=7

  由于 e [ 4 ] [ 1 ] + e [ 1 ] [ 3 ] = 5 + 6 = 11 < e [ 4 ] [ 3 ] = 12 e[4][1]+e[1][3]=5+6=11<e[4][3]=12 e[4][1]+e[1][3]=5+6=11<e[4][3]=12,所以更新矩阵e[4][3]=11

  更新后的矩阵如下所示:

Floyd算法求解最短路径

  接下来,求只允许经过1号和2号两个顶点的情况下任意两点之间的最短路径。我们需要在只允许经过1号顶点时任意两点的最短路径的结果下,再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短,即判断e[i][2]+e[2][j]是否小于e[i][j]

//经过2号顶点中转
for (int i = 1; i <=N ; i++) {
    for (int j = 1; j <=N; j++) {
        if(e[i][j]>e[i][2]+e[2][j]){
            e[i][j]=e[i][1]+e[1][j];
        }
    }
}

  由于 e [ 1 ] [ 2 ] + e [ 2 ] [ 3 ] = 2 + 3 = 5 < e [ 1 ] [ 3 ] = 6 e[1][2]+e[2][3]=2+3=5<e[1][3]=6 e[1][2]+e[2][3]=2+3=5<e[1][3]=6,所以e[1][3]=5

  由于 e [ 4 ] [ 2 ] + e [ 2 ] [ 3 ] = 7 + 3 = 10 < e [ 4 ] [ 3 ] = 11 e[4][2]+e[2][3]=7+3=10<e[4][3]=11 e[4][2]+e[2][3]=7+3=10<e[4][3]=11,所以e[4][3]=10

Floyd算法求解最短路径

  以此类推,后面的就不再一个个写了。

  总结:Floyd算法可以算出任意两点的最短路径,可以处理带有负权边的图,但不能处理带有“负环”的图。时间复杂度: O ( n 3 ) O(n^3) O(n3)

3、算法实战

3.1 算法描述

  小明喜欢观景,图示今天来到了蓝桥公园。

  已知公园有N个景点,景点和景点之间一共有M条道路,小明有Q个观景计划。每个计划包含一个起点st和一个终点ed,表示他想从st去到ed。但是小明体力有限,对于每个计划他想走最少的路完成,你可以帮帮他吗?

输入描述

  输入第一行包含三个正整数N,M,Q

  第2到M+1行每行包含三个正整数u,v,w,表示 u ↔ v u\leftrightarrow v uv之间存在一条距离为w的路。

  第M+2到M+Q-1行每行包含两个正整数st,ed,其含义如题所述。
1 ≤ N ≤ 400 , 1 ≤ M ≤ N × ( N − 1 ) 2 , Q ≤ 1 0 3 , 1 ≤ u , v , s t , e d ≤ n , 1 ≤ w ≤ 1 0 9 1\le N\le 400,1\le M\le \frac{N\times (N-1)}{2} ,Q\le 10^3 ,1\le u,v,st,ed\le n,1\le w\le 10^9 1N400,1M2N×(N1),Q103,1u,v,st,edn,1w109
输出描述

  输出共Q行,对应输入数据中的查询。

  若无法从st到达ed则输出-1。

输入输出样例

输入

3 3 3
1 2 1
1 3 5
2 3 2
1 2
1 3
2 3

输出

1
3
2

3.2 解题思路

  使用Floyd算法求解,由于该算法时间复杂度为 O ( n 3 ) O(n^3) O(n3),n较大会超时,但是本题的n比较小,所以够用。

  对于图中的任意两个点i和j,我们dist[i][j]表示从i到j的距离。初始时候,对于所有的 1 ≤ i , j ≤ n 1\le i,j\le n 1i,jn,有 d i s t [ i ] [ j ] = ∞ dist[i][j]=\infty dist[i][j]=,如果存在边(i,j),则dist[i][j]=w(i,j)。然后我们用动态规划思想逐步优化dist数组,使得dist[i][j]不断逼近真实的最短路径长度。

  我们主要是维护一个二维数组dist,dist[i][j]表示从i到j的最短路径长度。初始时,如果i和j之间有边,则dist[i][j]为该边(i,j)的权值,否则 d i s t [ i ] [ j ] = ∞ dist[i][j]= \infty dist[i][j]=。然后从1到n的每个点作为中转点,更新所有可能的最短路径长度。具体的说,对于中转点k,我们遍历所有的i,j,如果dist[i][j]>dist[i][k]+dist[k][j],则执行更新dist[i][j]=dist[i][k]+dist[k][j]。最后得到的dist数组即为任意两点之间的最短路径长度。

  我们对每个点当作中转点都要做双重for循环,所以在外层再加一个循环,只需要使用三重循环依次枚举中转点k和每对起点i和终点j,并更新dist[i][j]的值即可。

3.3 代码实现

import java.util.Arrays;
import java.util.Scanner;

public class Floyd {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();//N个景点
        int M = scan.nextInt();//经典之间共M条路
        int Q = scan.nextInt();//Q个观景计划
        long[][] dist = new long[N + 1][N + 1];
        for (int i = 1; i <=M ; i++) {  //初始化为最大值
            Arrays.fill(dist[i],Long.MAX_VALUE);
            dist[i][i]=0; //对角线赋值0即可(自己到自己)
        }
        for (int i = 1; i <=M; i++) {  //初始化两点距离
            int u = scan.nextInt();
            int v = scan.nextInt();
            long w = scan.nextLong();
            dist[u][v]=Math.min(dist[u][v],w);
            dist[v][u]=Math.min(dist[v][u],w);
        }
        //Floyd算法
        for (int k = 1; k <=N; k++) {
            for (int i = 1; i <=N ; i++) {
                for (int j = 1; j <=N; j++) {
                    if(dist[i][j]>dist[i][k]+dist[k][j]){
                        dist[i][j]=dist[i][k]+dist[k][j];
                    }
                }
            }
        }
        //查询
        for (int i = 0; i <Q ; i++) {
            int start = scan.nextInt();
            int end = scan.nextInt();
            if(dist[start][end]>=Long.MAX_VALUE){
                System.out.println(-1);
            }else{
                System.out.println(dist[start][end]);
            }
        }
    }
}

   真正的算法就5~6行,还是比较好理解的。

Floyd算法求解最短路径文章来源地址https://www.toymoban.com/news/detail-451233.html

到了这里,关于Floyd算法求解最短路径的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【路径规划】(2) A* 算法求解最短路,附python完整代码

    大家好,今天和各位分享一下机器人路径规划中非常经典的 A* 算法,感兴趣的点个关注,文末有 python 代码,那我么开始吧。 A* 算法是 1968 年 P.E.Hart[1]等人所提出的 在全局地图环境中所有已知情形下求解最短路径问题的方法,由于其简洁高效,容易实施 等 优点 而受到人们

    2024年02月03日
    浏览(36)
  • Acwing.854 Floyd求最短路 (Floyd算法)

    给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。 再给定k个询问,每个询问包含两个整数x和y,表示查询从点x到点y的最短距离,如果路径不存在,则输\\\"impossible”。 数据保证图中不存在负权回路。 第一行包含三个整数n, m, k 接下来m行,每行包含三

    2024年02月13日
    浏览(36)
  • 图算法——求最短路径(Floyd算法)

    目录 一、什么是最短路径 二、弗洛伊德(Floyd)算法 三、测试程序         求图的最短路径在实际生活中有许多应用,比如说在你在一个景区的某个景点,参观完后,要怎么走最少的路程到你想参观的下个景点,这就利用到了求图最短路径的算法。求图的最短路径有很多

    2024年02月07日
    浏览(38)
  • 【MATLAB】最短路径Floyd算法

    1.1适用范围 ∙ bullet ∙ 求每队顶点的最短路径 ∙ bullet ∙ 有向图、无向图和混合图 1.2算法思想 直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1),D(2)…D(n)( 每次加入一个点然后更新最短路径矩阵D ),D(n)是图的最短距离矩阵,同时引入一个后继

    2024年02月16日
    浏览(32)
  • 算法——图论——最短路径——Floyd / 传递闭包

    目录  Floyd-Warshall(弗洛伊德)算法 传递闭包 一、试题 算法训练 盾神与离散老师2    求所有顶点到所有顶点的最短路径问题 弗洛伊德算法(Floyd-Warshall algorithm)是一种用于寻找图中所有顶点对之间最短路径的动态规划算法。 该算法可以处理带有负权边但不含负权环的加权

    2024年02月20日
    浏览(40)
  • 数据结构--最短路径 Floyd算法

    F l o y d 算法:求出每⼀对顶点之间的最短路径 color{red}Floyd算法:求出每⼀对顶点之间的最短路径 Fl oy d 算法:求出每 ⼀ 对顶点之间的最短路径 使⽤动态规划思想,将问题的求解分为多个阶段 对于n个顶点的图G,求任意⼀对顶点 V i → V j V_i to V_j V i ​ → V j ​ 之间的最短

    2024年02月12日
    浏览(38)
  • 多源最短路径算法:Floyd-Warshall算法分析

    在有向赋权图中(可以存在 带负权值的路径 ,但不能存在 总权值为负数的环路 ),Floyd-Warshall算法可以求出 任意两个顶点间 的最短路径 假设图中有 N 个顶点,顶点按照 0~N-1 进行编号 算法中使用 二维数组 Dist 来记录点与点之间的最短路径长度, Dist[i][j] 表示第i个顶点到第j个顶点

    2024年02月09日
    浏览(39)
  • 弗洛伊德(Floyd's)算法—解决最短路径经典算法

    弗洛伊德算法(Floyd\\\'s algorithm)是一种用于解决图中最短路径问题的经典算法。由美国计算机科学家罗伯特·弗洛伊德于1962年提出,该算法通过动态规划的思想,在图中寻找任意两个节点之间的最短路径,具有广泛的应用。本文将详细介绍弗洛伊德算法的原理、实现细节以及应用

    2024年02月04日
    浏览(39)
  • 图论:最短路(dijkstra算法、bellman算法、spfa算法、floyd算法)详细版

    终于是学完了,这个最短路我学了好几天,当然也学了别的算法啦,也是非常的累啊。 话不多说下面看看最短路问题吧。 最短路问题是有向图,要求的是图中一个点到起点的距离,其中我们要输入点和点之间的距离,来求最短路。 下面分为几类题目: 单源汇最短路--一个起

    2024年01月21日
    浏览(43)
  • Floyd_Warshall算法详解及实现(多源最短路径)

    小明要去这样的城市旅游(城市交通图如下),为了减轻经济负担,小明想知道任意两个城市之间的最短路径。 从图中,可以得到:小明打算去4个城市(节点数)旅游,而这4个城市之间有8条公路(边数)连通,公路上的数字(权重)表示这条公路的长短。 现在需要设计一

    2023年04月17日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包