当前位置：首页 > article >正文

Floyd求解最短路径问题

article 2025/3/11 10:01:07

题目链接：

4.蓝桥公园 - 蓝桥云课

题目描述：

小明喜欢观景，于是今天他来到了蓝桥公园。已知公园有 N 个景点，景点和景点之间一共有 M 条道路。小明有 Q 个观景计划，每个计划包含一个起点 st 和一个终点 ed，表示他想从 st 去到 ed。但是小明的体力有限，对于每个计划他想走最少的路完成，你可以帮帮他吗？

输入描述：

输入第一行包含三个正整数 N,M,Q。第 2 到 M+1 行每行包含三个正整数 u,v,w，表示 u↔v 之间存在一条距离为 w 的路。第 M+2 到 M+Q−1 行每行包含两个正整数 st,ed 其含义如题所述。1≤N≤400，1≤M≤N×(N−1)/2，Q≤103，1≤u,v,st,ed≤n，1≤w≤10^9

输出描述：

输出共 Q 行，对应输入数据中的查询。若无法从 st 到达 ed 则输出 -1。

输入：

输出：

1
3
2

解题思路：

Floyd：利用三层循环来更新邻接矩阵，其中最外层依次是0-N-1的中间点，第二层为起点，最后一层为终点，当起点到终点的直接路径大于起点-中间点-终点的间接路径，则更新为更短的路径，这样最终就可以得到每个点到其余点最段的路径长度的邻接矩阵。

代码：

1、Floyd代码

//Floyd
void Floyd(int N)
{
	//k是中间点
	for (int k = 0;k < N;k++)
	{
		//v是起点
		for (int v = 0;v < N;v++)
		{
			//w是终点
			for (int w = 0;w < N;w++)
			{
				if (D[v][k] + D[k][w] < D[v][w])     //中间点有用
				{
					D[v][w] = D[v][k] + D[k][w];   //更新D
					D[w][v] = D[v][k] + D[k][w];    //无向图
				}
			}
		}
	}
}

2、完整代码

#include <iostream>
#define MAX 10000000000
using namespace std;

long long D[410][410];     //创建邻接矩阵

//初始化邻接矩阵
void Init_D(int N)
{
	for (int i = 0;i < N;i++)
	{
		for (int j = 0;j < N;j++)
		{
			if (i == j)
			{
				D[i][j] = 0;
			}
			else
			{
				D[i][j] = MAX;
			}
		}
	}
}

//Floyd
void Floyd(int N)
{
	//k是中间点
	for (int k = 0;k < N;k++)
	{
		//v是起点
		for (int v = 0;v < N;v++)
		{
			//w是终点
			for (int w = 0;w < N;w++)
			{
				if (D[v][k] + D[k][w] < D[v][w])     //中间点有用
				{
					D[v][w] = D[v][k] + D[k][w];   //更新D
					D[w][v] = D[v][k] + D[k][w];    //无向图
				}
			}
		}
	}
}


int main()
{
	// 请在此输入您的代码
	//输入
	int N, M, Q;
	cin >> N >> M >> Q;

	//对矩阵进行初始化
	Init_D(N);    

	//得到点与点之间的关系二维矩阵
	for (int i = 0;i < M;i++)
	{
		int u, v;
		long long w;
		cin >> u >> v >> w;
		if (D[u - 1][v - 1] > w) 
		{
			D[u - 1][v - 1] = w;
			D[v - 1][u - 1] = w;
		}
	}

	//更新D
	Floyd(N);

	//输出
	for (int i = 0;i < Q;i++)
	{
		int st, ed;
		cin >> st >> ed;
		if (D[st - 1][ed - 1] != MAX) //存在路径
		{
			cout << D[st - 1][ed - 1] << endl;
		}
		else
		{
			cout << "-1" << endl;
		}
	}
	return 0;
}