最短路径之Flody算法（邻接矩阵存图）

（一） Flody算法

【前言】：前面的Dijkstra算法用来解决单源最短路径的问题，即：从指定点到图上其他各点的最短路径。那么，如果我们要求图中任意两个结点之间的最短路径，如何用算法来实现呢？如果用Dijkstra来实现，就需要每次改变源点，再使用多个dis数组来记录，这样，问题就会变得很复杂。那么，有没有一种简单的算法来求图中任意两个结点之间的最短路径呢？当然有！那就是 Flody算法。

利用类似三角形定理：三角形的任意两边之和大于或等于第三边；

【算法思想】：求A到B的最短路径，Flody算法的核心思想就是找到一个中转站C，使得从A到C再到B的距离比从A直接到B的距离短；
核心算法就是在N个结点中找到每次合适的一个中转站k：

	for (k = 0; k < n; k++)//在n个结点中依次找中转站；
	{
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < n; j++)
			{
				if (mp[i][j] > mp[i][k] + mp[k][j])//如果直接从i到j的距离大于从i到k再到j的距离，即找到一个合适的中转站，就更新地图；
				{
					mp[i][j] = mp[i][k] + mp[k][j];
				}
			}
		}
	}

例如：

有向图：

完整代码实现如下：

#include<iostream>
using namespace std;
#define N 1000
int mp[N][N];//用邻接矩阵来存图
#define INF 0x3f3f3f3f
void inin(int n)//初始化，结点自己和自己之间的距离为0，其他的为无穷大；
{
	int i, j;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (i == j)
				mp[i][j] = 0;
			else
			{
				mp[i][j] = INF;
			}
		}
	}
}
void flody(int n)//核心算法
{
	int k, i, j;
	for (k = 0; k < n; k++)//在n个结点中依次找中转站；
	{
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < n; j++)
			{
				if (mp[i][j] > mp[i][k] + mp[k][j])//如果直接从i到j的距离大于从i到k再到j的距离，即找到一个合适的中转站，就更新地图；
				{
					mp[i][j] = mp[i][k] + mp[k][j];
				}
			}
		}
	}
}
int main()
{
	int n, m;
	int i, j,k;
	cin >> n >> m;//n个结点m条边
	inin(n);
	for (i = 0; i < m; i++)//注意：这里是有向图；如果是无向图，则加上：mp[b][a]=c;
	{
		int a, b, c;
		cin >> a >> b >> c;
		mp[a][b] = c;
	}
	flody(n);
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			cout << i << "---->" << j << ":";//输出从i到j的最短路径；
			if (mp[i][j] == INF)
				cout << "oo"<<endl;//oo表示无穷大，即不联通；
			else
			cout << mp[i][j] << endl;
		}
	}
	return 0;
}

输入：

4 6
0 1 5
0 2 2
0 3 7
1 2 6
1 3 1
2 3 2

输出：

起点 终点 最短路径
0 ----> 0: 0
0 ----> 1: 5
0 ----> 2: 2
0 ----> 3: 4
1 ----> 0: oo
1 ----> 1: 0
1 ----> 2: 6
1 ----> 3: 1
2 ----> 0: oo
2 ----> 1: oo
2 ----> 2: 0
2 ----> 3: 2
3 ----> 0: oo
3 ----> 1: oo
3 ----> 2: oo
3 ----> 3: 0

最后

以上就是时尚棒球为你收集整理的最短路径之Flody算法（邻接矩阵存图）的全部内容，希望文章能够帮你解决最短路径之Flody算法（邻接矩阵存图）所遇到的程序开发问题。

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