Floyd求最短路（Floyd算法）

参考：约会怎么走到目的地最近呢？一文讲清所有最短路算法问题-CSDN博客

有4个城市8条路，公路上的数字表示这条公路的长短，并且路是单向的，现在要求我们求出任意两个城市之间的最短路程，也就是求任意两个点之间的最短路经，这就是多源最短路问题。

1.假设我们只允许经过1号城市，求任意两城市之间的最短路程，应该如何求呢？

只需判断e[ i ][1]+e[1][ j ]是否比e[ i ][ j ]要小即可。

for(int i=1;i<=n;++i)   //遍历起点城市
	for(int j=1;j<=n;++j) //遍历被缩小距离的城市
		if(e[i][j] > e[i][1]+e[1][j]) //如果我通过1城市进行中转后的距离比你现在直接到要近
			e[i][j]=e[i][1]+e[1][j];//则直接赋值给给e[i][j]即可

2.假设我们允许经过1号城市和2号城市，求任意两点之间的最短路程，应该如何求呢？

我们需要在只允许经过 1号顶点时任意两点的最短路程的结果下，再判断如果经过2号顶点是否可以使得 i 号顶点到 j 号顶点之间的路程变得更短，即判断e[ i ][2]+e[2][ j ] 是否要比 e[ i ][ j ] 要小。
?

//经过一号顶点
for(int i=1;i<=n;++i)//遍历起点城市
	for(int j=1;j<=n;++j)//遍历被缩小距离的城市
		if(e[i][j] > e[i][1]+e[1][j])//如果我通过1城市进行中转后的距离比你现在直接到要近
			e[i][j]=e[i][1]+e[1][j];//则直接赋值给给e[i][j]即可
			
//经过二号顶点
for(int i=1;i<=n;++i)//遍历起点城市
	for(int j=1;j<=n;++j)//遍历被缩小距离的城市
		if(e[i][j] > e[i][2]+e[2][j])//如果我通过2城市进行中转后的距离比你现在直接到要近
			e[i][j]=e[i][2]+e[2][j];//则直接赋值给给e[i][j]即可

?以此类推，如果我们允许经过从1号到n号所有城市求两点间最短路程，可以写出代码：

for(int k=1;k<=n;k++) //一共有n个城市
    {
        for(int i=1;i<=n;i++)  //遍历起点城市
        {
            for(int j=1;j<=n;j++)  //遍历需要缩短距离的城市
            {
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);  //经过k号城市进行中转的距离与原来直接从起点到终点的距离是否有缩小
            }
        }
    }

这也就是Floyd算法了，Floyd属于多源最短路径算法，能够求出任意2个顶点之间的最短路径，支持负权边。

题目描述

给定一个?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^2
1≤m≤20000,
图中涉及边长绝对值均不超过?1000010000。

输入样例：

3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

输出样例：

impossible
1

思路：就像上面一样，遍历所有点，求从起点经过中间的点中转后到终点的最短距离

for(int k=1;k<=n;k++) //一共有n个城市
    {
        for(int i=1;i<=n;i++)  //遍历起点城市
        {
            for(int j=1;j<=n;j++)  //遍历需要缩短距离的城市
            {
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);  //经过k号城市进行中转的距离与原来直接从起点到终点的距离是否有缩小
            }
        }
    }

示例代码：

// 这道题是多源点问题，有多个x到y的路径要求
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=210,INF=1e9; //表示正无穷
int n,m,q;
int d[N][N]; //d[i][j]表示从i到j的最短路长度

void floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) d[i][j]=0;  //自环边的权值设成了0，是为了干掉自环（因为不存在负权回路，自环没有意义）
            else d[i][j]=INF;
        }
    }
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        d[a][b]=min(d[a][b],c);  //输入每条边，只保留最短边
    }
    floyd();
    
    while(q--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        int t=d[a][b];
        if(t>INF/2) puts("impossible"); //不能走到终点，但由于负数边权的存在，终点的距离可能被其他长度是正无穷的距离更新
        else printf("%d\n",t);
    }
    return 0;
}