最短路-Floyd 配题（HDU 2066）

Floyd最短路算法属于多源最短路，可以求出图中任意两点的最短路径。如果图中存在负权但是不存在负环的话Floyd是可以解决最短路问题的。

Floyd算法返回最短路径：多源最短路，需要二维空间的数组来存储所有的最短路径，path[i][j]，其中 i 表示起点，j 表示终点，那么path[i][j]表示以 j 为终点，i 为起点的最短路径上点 i 的下一个节点。那么在初始化过程中path[i][j] = j，在更新过程中path[i][j] = path[i][k]。

对于Floyd算法，最困难的地方就是时间复杂度的问题，所以如果可以剪枝，要养成良好的代码习惯。

题目：HDU 2066（中文题目非常好理解）

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int max_n = 1000+1;
const int INF = 10000000;
int graph[max_n][max_n];
int neighbor_city[max_n];
int love_city[max_n];
int T, S, D;
int floyd(int max_index)
{
	for (int k = 1; k <= max_index; k++)
	{
		for (int i = 1; i <= max_index; i++)
		{
			if (graph[i][k] == INF) continue; // 这是一个显而易见的剪枝，但是如果没有剪枝意识的话，总是会忽略的
			for (int j =

最后

以上就是碧蓝仙人掌为你收集整理的最短路-Floyd 配题（HDU 2066）的全部内容，希望文章能够帮你解决最短路-Floyd 配题（HDU 2066）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。