码创造者

这个屌丝很懒，什么也没留下！

热门标签

Floyd算法求最短路径_floyd最短路径算法

作者：码创造者 | 2024-06-18 20:04:13

踩

floyd最短路径算法

一.Floyd算法介绍

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

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

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

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

上述概念来源于百度百科

Floyd算法可以用来求图结构中任意两点的最短路径，即“多源最短路径”问题。

二.算法实现

对于实现Floyd算法，我们通常需要通过邻接矩阵（二维数组）的实现。

一.邻接矩阵介绍

邻接矩阵就是利用二维矩阵表示图中各顶点之间的关系，对于有n个顶点的图来说，用n阶方阵来表示该图，其中矩阵元素 $A_{ij}$ 表示从顶点 $v_{i}$ 到 $v_{j}$ 之间的边， $A_{ij}$ 的大小表示边的权值。如果顶点 $v_{i}$ 到 $v_{j}$ 没有边，则可以将 $A_{ij}$ 设置为0或者 $\infty$ 。

例如在该图中，任意一点（i，j）代表着，从i和j边的权（特定情景可能是距离，消费），通常我们将所以点初始化为无穷大，自己指向自己的点为0。

二.过程简述

如果要让任意两点之间(假设是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。通过以上分析，我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。

通过以上过程的分析，我们最终可以得到一个邻接矩阵。

三.Floyd核心代码

Floyd算法的核心代码非常简洁只有短短5行。


for (int k = 1; k <= n; k++) {       //注意中转点在循环的最外层
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (e[i][j] > e[i][k] + e[k][j])   //如果当前小于重组后
				e[i][j] = e[i][k] + e[k][j];   //将当前值替代
		}
	}
}

三.例题分析

一.B3647 【模板】Floyd.

https://www.luogu.com.cn/problem/B3647

题目描述

给出一张由 n 个点 m 条边组成的无向图。

求出所有点对 (i,j) 之间的最短路径。

输入格式

第一行为两个整数 n,m，分别代表点的个数和边的条数。

接下来 m 行，每行三个整数 u,v,w，代表 u,v 之间存在一条边权为 w 的边。

输出格式

输出 n 行每行 n 个整数。

第 i 行的第 j 个整数代表从 i 到 j 的最短路径。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

对于 100% 的数据，n≤100，m≤4500，任意一条边的权值 w 是正整数且 1⩽w⩽1000。

数据中可能存在重边。

本题是Floyd算法的模版题，我们只要照着刚才的过程模拟写就可以。


#include<bits/stdc++.h>
 
using namespace std;
#define MAX 5000         //宏定义一个很大的数，代表无穷大
int a[MAX][MAX];         //邻接矩阵
 
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)   //初始化邻接矩阵
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j)
                a[i][j]=0;  //对角线上的点（自己指向自己）赋值为0
            else
                a[i][j]=MAX;//没有边联通的点赋值为无穷大
        }
    }
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        a[u][v]=min(a[u][v],w);   //无向边，所以关于对角线对称
        a[v][u]=min(a[v][u],w);   //因为可能有重边，所以取最小
    }
    for(int k=1;k<=n;k++)        //Floyd算法核心代码段
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                a[i][j]=min(a[i][k]+a[k][j],min(a[i][j],a[j][i]));  //找到最短进行赋值
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<a[i][j]<<" ";    //遍历输出邻接矩阵
        }
        cout<<endl;
    }
    return 0;
}

二.P2835 刻录光盘

https://www.luogu.com.cn/problem/P2835

题目描述

在JSOI2005夏令营快要结束的时候，很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家，以便大家回去后继续学习。组委会觉得这个主意不错！可是组委会一时没有足够的空光盘，没法保证每个人都能拿到刻录上资料的光盘，又来不及去买了，怎么办呢？！

组委会把这个难题交给了LHC，LHC分析了一下所有营员的地域关系，发现有些营员是一个城市的，其实他们只需要一张就可以了，因为一个人拿到光盘后，其他人可以带着U盘之类的东西去拷贝啊！

可是，LHC调查后发现，由于种种原因，有些营员并不是那么的合作，他们愿意某一些人到他那儿拷贝资料，当然也可能不愿意让另外一些人到他那儿拷贝资料，这与我们JSOI宣扬的团队合作精神格格不入！！！

现在假设总共有N个营员（2<=N<=200），每个营员的编号为1~N。LHC给每个人发了一张调查表，让每个营员填上自己愿意让哪些人到他那儿拷贝资料。当然，如果A愿意把资料拷贝给B，而B又愿意把资料拷贝给C，则一旦A获得了资料，则B，C都会获得资料。

现在，请你编写一个程序，根据回收上来的调查表，帮助LHC计算出组委会至少要刻录多少张光盘，才能保证所有营员回去后都能得到夏令营资料？

输入格式

先是一个数N，接下来的N行，分别表示各个营员愿意把自己获得的资料拷贝给其他哪些营员。即输入数据的第i+1行表示第i个营员愿意把资料拷贝给那些营员的编号，以一个0结束。如果一个营员不愿意拷贝资料给任何人，则相应的行只有1个0，一行中的若干数之间用一个空格隔开。

输出格式

一个正整数，表示最少要刻录的光盘数。

输入输出样例

输入 #1复制

输出 #1复制

这道题我是通过并查集和Floyd联合起来使用的，通过题意我们知道这里的关系图是单向的，我们只需要使用Floyd算法的，将原意共享的人通过邻接矩阵表示出来，然后通过并查集查找出分为多少个集体，统计集体个数就可以了。


#include<bits/stdc++.h>
using namespace std;
#define MAX 205
bool vis[MAX][MAX]; //邻接矩阵
int pre[MAX];      //前驱数组
int n,ans=0;
 
void solve()
{
    for(int i=1;i<=n;i++)
    {
        int x;
        while(1)
        {
            cin>>x;
            if(x!=0)    //果然x值不为0，说明他愿意拷贝给x
                vis[i][x]=1;   //将代表i原意拷贝给x的点赋为1
            else
                break;
        }
    }
    for(int k=1;k<=n;k++)   //Floyd算法核心代码段
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(vis[i][k]&&vis[k][j])   //如果i原意给k，k愿意给j
                    vis[i][j]=1;           //那么相当于i愿意给j
            }
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        pre[i]=i;             //初始化前驱数组
    solve();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(vis[i][j])    //如果邻接矩阵中的点不为0，说明i原意给j拷贝
                pre[j]=pre[i];  //将j的前驱改为i的前驱
        }
    }
    for(int i=1;i<=n;i++)
        if(pre[i]==i)        //如果找到一个小集体（即前驱是自己）
            ans++;           //光盘数加一
    cout<<ans<<endl;
    return 0;
}

四.Floyd算法的优缺点

优点：Floyd算法容易理解，代码简洁，可以处理图结构中任意两点的最短路径。Floyd算法可以处理带有负权边（边的值为负数）的图。

缺点：Floyd算法的时间复杂度是O(N^3)，时间复杂度很高。并且不能处理带有“负权回路”的图。

今天的博客就到这里了！~QVQ~

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/码创造者/article/detail/734569