图的最短路径算法Floyed
带权图
如下图所示，我们把边带有权值的图称为带权图。边的权值可以理解为两点之间的距离。一张图中任意两点间会有不同的路径相连。最短路径就是指连接两点的这些路径中最短的一条。
国庆期间有一个人计划旅行，地图如下图所示，这个人希望在出发前知道任意两个城市之间的最短路径
如何求解任意两点间最短路径呢？
我们很容易想到，通过深度或者广度优先搜索可以求出两点之间的最短路径。有没有别的办法?
下面来讲解floyed算法：
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。二维数组如下：
假设现在只允许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号中转的情况下任意两点之间的最短路径更新为：
接下来，求在只允许经过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号的中转的情况下，任意两点之间的最短路径更新为：
我们可以将以上情况写成三个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算法可以算出任意两点的最短路径，可以处理带有负权边的图，但不能处理带有“负环”的图。
负环就是累加起来为一个负数
时间复杂度：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
代码如下：
#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; // 程序结束
}