`Floyd`最短路算法(初版)

今天，我们来讲讲在最短路中的第三种算法，floyd算法, 实际上这是第五个基础算法，

dijstkra算法有朴素算法形式的，也有堆优化版的，它有两种形式

在处理负权边的时候有boolman_ford算法和优化版的spfa算法

所以这实际上是第五种了((^_^))

算法来源

在计算机科学中，Floyd算法是一种在具有正或负边缘权重（但没有负周期）的加权图中找到最短路径的算法。算法的单个执行将找到所有顶点对之间的最短路径的长度（加权）。虽然它不返回路径本身的细节，但是可以通过对算法的简单修改来重建路径。该算法的版本也可用于查找关系R的传递闭包，或（与Schulze投票系统相关）在加权图中所有顶点对之间的最宽路径。

<来源于百度百科>

floyd算法主要是来处理最短路问题中的多个点之间的距离，在需要使用这种算法的题目上会出现多次询问,让你求a点到b点的最短距离，包括负权边和闭环

下面以一道题目为例，来说明这个算法在处理实际题目上的应用

例题:`Floyd`求最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定 k 个询问，每个询问包含两个整数 x 和y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。

数据保证图中不存在负权回路。

输入格式

第一行包含三个整数 n,m,k

接下来 m 行，每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边，边长为z

接下来 k 行，每行包含两个整数 x,y表示询问点 x 到点 y的最短距离

输出格式

共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。

数据范围

1≤n≤200
1≤k≤n
1≤m≤20000
图中涉及边长绝对值均不超过 10000

输入样例

输出样例

impossible
1

算法思想

(详见动态规划)

(作者还没有学动态规划……)

下面介绍引自百度百科

路径矩阵

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

从图的带权邻接矩阵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]这条路

算法构建

首先，这道题有q次询问，一共有m条边，n个点

q次询问就需要我们对于每一个点都需要进行分析，我们设立一个三维数组d[k,i,j], 这个三维数组的意思是从i开始,只经过1到k这些中间点后到达j的最短距离

它可以用一个等式来表示

d[k,i,j] = d[k-1,i,k] + d[k-1,k,j]

右半部分表示的是从i开始，只经过1到k-1这些中间点后到达k的最短距离与从k这个点开始，只经过1到k-1这些中间点到达j的最短距离之和可以用来表示左边的三维数组，右边实际上就是一个累加的过程，类似于dp方程的记忆化搜索，可以将一个邻接矩阵转换成邻接表的形式

代码优化

d[i][j] = min(d[i][j],d[i][k]+d[k][j])

定义类代码

变量初始化

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 210, INF = 1e9;
//n个点 m条路 q次询问
int n, m, q;
//d数组表示的是从某个点到某个点的距离
int d[N][N];

输入输出

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    int i, j;
    //初始化i号点到j号店的距离
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        	//每一行的1号点上的i和j是相等的，初始化为0
            if (i == j) d[i][j] = 0;
            //其它点不确定，初始化为正无穷(其实也没有那么大)
            else d[i][j] = INF;
    }
    while (m--)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        //排除自环正权边和重边(重边取最小值)
        d[a][b] = min(d[a][b], w);
    }
    //进入floyd算法
    floyd();
    //q次询问
    while (q--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        //不能够找到距离
        if (d[a][b] > INF / 2) puts("impossible");
        //能够找到距离
        else printf("%d\n", d[a][b]);
    }
    return 0;
}

算法代码化

void floyd()
{
    int i, j, k;
    for (k = 1; k <= n; k++)
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)
            	//邻接矩阵转邻接表
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}