图的最短路径算法Floyed

带权图

如下图所示，我们把边带有权值的图称为带权图。边的权值可以理解为两点之间的距离。一张图中任意两点间会有不同的路径相连。最短路径就是指连接两点的这些路径中最短的一条。
在这里插入<a class= 图片描述" />
国庆期间有一个人计划旅行，地图如下图所示，这个人希望在出发前知道任意两个城市之间的最短路径
图片描述" />
如何求解任意两点间最短路径呢？
我们很容易想到，通过深度或者广度优先搜索可以求出两点之间的最短路径。有没有别的办法?
下面来讲解floyed 算法：

floyed_8">floyed 算法

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

我们首先将这个图存储起来，我们使用二维数组

比如1号城市到3号城市距离为6即e[1][3]=6,假如2无法到达4我们就表示为e[2][4]=∞，我们再设当前1号城市到1号城市距离为0，e[1][1]=0。二维数组如下：
在这里插入<a class= 图片描述" />
假设现在只允许1号顶点中转，求任意两点之间(i到j)的最短路径。
现在只需判断e[i][1]+e[1][j]是否比e[i][j]小，代码如下：

#include<iostream>
using namespace std;
int main()
{
	int e[10][10];
	int n,i,j;
	//经过1号顶点中转
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
		{
			if (e[i][j] > e[i][1] + e[1][j])
			{
				e[i][j] = e[i][1] + e[1][j];
			}
		}
	}
}

在只经过1号中转的情况下任意两点之间的最短路径更新为：
在这里插入<a class= 图片描述" />
接下来，求在只允许经过1和2号两个顶点的情况下任意两点之间的最短路径。怎么求呢?我们需要在只允许经过1号顶点时任意两点的最短路径的结果下，再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短，即判断e[i][2]+e[2][]是否比e[i]i]要小，代码如下：

#include<iostream>
using namespace std;
int main()
{
	int e[10][10];
	int n,i,j;
	//经过1号顶点中转
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
		{
			if (e[i][j] > e[i][1] + e[1][j])
			{
				e[i][j] = e[i][1] + e[1][j];
			}
		}
	}
	//经过2号顶点中转
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
		{
			if (e[i][j] > e[i][2] + e[2][j])
			{
				e[i][j] = e[i][2] + e[2][j];
			}
		}
	}
}

在只经过1号和2号的中转的情况下，任意两点之间的最短路径更新为：
在这里插入<a class= 图片描述" />
我们可以将以上情况写成三个for循环代码如下：

#include<iostream>
using namespace std;
int main()
{
	int e[10][10];
	int n,i,j,k;	
	for (k = 1; k <= n; k++)
	{
		for (i = 1; i <= n; i++)
		{
			for (j = 1; j <= n; j++)
			{
				if (e[i][j] > e[i][k] + e[k][j])
				{
					e[i][j] = e[i][k] + e[k][j];
				}
			}
		}
	}

}

注意：中间的点的变量k必须放在最外面一层循环。

Floyed算法总结：

Floyed算法可以算出任意两点的最短路径，可以处理带有负权边的图，但不能处理带有“负环”的图。
负环就是累加起来为一个负数
在这里插入<a class= 图片描述" />
时间复杂度：O(n^3)

最短路径问题

【问题描述】

平面上有n个点(n<=100)，每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。

【输入格式】

输入文件为short.in，共n+m+3行，其中：
第一行为整数n。
第2行到第n+1行(共n行)，每行两个整数x和y，描述了一个点的坐标。
第n+2行为一个整数m，表示图中连线的个数。
此后的m行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。最后一行：两个整数s和t，分别表示源点和目标点。

【输出格式】

输出文件为short.out.仅一行一个实数（保留两位小数），表示从s到t的最短路径长度。

输入样例

5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5

输出样例

3.41

在这里插入<a class= 图片描述" />

代码如下：

#include<iostream>  // 引入标准输入输出库
#include<cmath>     // 引入数学库，用于计算平方根
#include<cstring>   // 引入字符串处理库，用于数组的初始化
using namespace std;

int a[101][3];      // 存储每个节点的坐标，最多 101 个节点，每个节点有两个坐标 x 和 y
double f[101][101]; // 存储两点之间的距离，f[i][j] 表示第 i 点和第 j 点之间的距离
int n, i, j, k, x, y, m, s, e; // n 为节点数量，m 为边的数量，s 为起点，e 为终点，x 和 y 为节点编号

int main()
{
    cin >> n;  // 输入节点数量
    // 循环输入每个节点的坐标
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i][1] >> a[i][2];  // 输入第 i 个节点的 x 和 y 坐标
    }

    cin >> m;  // 输入边的数量
    memset(f, 0x7f, sizeof(f));  // 初始化 f 数组，将其设为一个非常大的值（表示无穷大），避免误判最短路径

    // 输入每条边，计算并存储两个节点之间的欧氏距离
    for (i = 1; i <= m; i++)
    {
        cin >> x >> y;  // 输入两个节点编号
        // 计算两个节点之间的距离，使用欧氏距离公式 sqrt((x1 - x2)^2 + (y1 - y2)^2)
        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));
    }

    cin >> s >> e;  // 输入起点 s 和终点 e

    // 使用 Floyd-Warshall 算法求所有点对之间的最短路径
    for (k = 1; k <= n; k++)  // k 为中间点
    {
        for (i = 1; i <= n; i++)  // i 为起点
        {
            for (j = 1; j <= n; j++)  // j 为终点
            {
                // 如果通过中间点 k 到达终点的距离更短，则更新 f[i][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];  // 更新最短路径
                }
            }
        }
    }

    // 输出起点 s 到终点 e 的最短距离，保留两位小数
    printf("%.2lf\n", f[s][e]);

    return 0;  // 程序结束
}