Floyed-Warshall【弗洛伊德算法】

时间:2021-11-21 18:53:44

首先介绍一下有关最短路径的知识

从某顶点出发,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径叫做最短路径。解决最短路的问题有以下算法,Dijkstra算法,Bellman-Ford算法,Floyed算法和SPFA算法等。

                                                                                         ——百度百科

通俗点来说就是在图中的两点之间的最短距离(只不过这里规定了路径而已)


 

那么,我们的问题来了

什么是图? 

图(Graph【这也是为什么oier们通常设g数组的原因】)是表示物件与物件之间的关系的数学对象,是图论的基本研究对象。

简洁来说,就是一个神奇的表示关系的图表(别告诉我你们不知道图表是什么

什么是权值?

在数学领域,权值指加权平均数中的每个数的频数,也称为权数或权重。

也就是这条边的价值【类似于长度】

 


那么这里对于一些基本的概念性的知识应该是没有什么问题了

说实话这个算法是用来求多源最短路径的算法。

                  ——gh

                    ——题记【并Orz一波】

这里的算法原理可以看做是一个相对来说和DP有些关系的DP

这个神奇的算法的复杂度井然是O(n3)【令人十分慌张

但这个算法也有其一定的优点:


1.可以计算图中任意两点间的最短路径

2.适用于负边权的情况

…………【好处很多,我们要有一双善于发现好处的眼睛

 

核心代码类似于这个

for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if((i!=j)&&(i!=k)&&(j!=k)&&(f[i][k]+f[k][j]<f[i][j]))//这里是一步松弛操作,使得f[i][j]是最短的
                {
                    f[i][j]=f[i][k]+f[k][j];
                }
            }
        }
    }

其实很好理解

这里放一个最简单的例题给大家刷一刷吧

【洛谷P1744 采购特价商品】

这里很好理解

就直接放代码了

#include<bits/stdc++.h>
using namespace std;
int a[101][3];
double f[101][101];
int n,i,j,k,x,y,m,s,e;
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i][1]>>a[i][2];
    }
    cin>>m;
    memset(f,0x7f,sizeof(f));//将这个矩阵初始化一下
    for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        f[y][x]=f[x][y]=sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2));//这就是两点间距离公式了【注意需要强制类型转换】,因为是无向的,所以f[x][y]=f[y][x]
    }
    cin>>s>>e;
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if((i!=j)&&(i!=k)&&(j!=k)&&(f[i][k]+f[k][j]<f[i][j]))
                {
                    f[i][j]=f[i][k]+f[k][j];
                }
            }
        }
    }
    printf("%.2lf",f[s][e]);
}