Floyd All Shortest Path 所有最短路径的查找 C++程序

Floyd All Shortest Path 所有最短路径的查找在严慧敏这本书也有介绍，但是这本书是讲数据结构的，没有介绍这个算法是什么算法，其实这个算法是动态规划法。
思路：

1 用一个矩阵来记录从i到j的最短路径

2 用三层循环，选好一个点k，然后把所有其他点组成两对i和j；测试从i到j是直接走近，还是从i经过k最后到j比较近一点。如果绕道k之后花费更小一点，那么就更新[i][j]的数据。

3 循环完毕就记录了所有两点之间的最短距离了。

看下面的实现程序，用了两个循环，第一循环是赋值给记录最短路径的矩阵，第二个循环就是实际记录最短路径的算法。

用了两个矩阵，第二个矩阵是为了可以打印出来两点之间的最短路径都经过了那些点：

#include<iostream>
#include<vector>

using namespace std;
class Solution {
public:
    vector<vector<vector<int> > > FloydAllShortestPath(vector<vector<int> >& matrixGraph,
	    vector<vector<vector<int> > >& pathM)
    {
	    int n = matrixGraph.size();
	    vector<vector<vector<int> > > allPathNum(n);
	    pathM.resize(n);

	    for (int i = 0; i < n; i++)
	    {
		    allPathNum[i].resize(n);
		    pathM[i].resize(n);
		    for (int j = 0; j < n; j++)
		    {
			    allPathNum[i][j].resize(n+1);
			    allPathNum[i][j][0] = matrixGraph[i][j];
			    pathM[i][j].resize(n+1);
		    }
	    }
	    
	    for (int k = 0; k < n; k++)
	    {
		    for (int i = 0; i < n; i++)
		    {
			    for (int j = 0; j < n; j++)
			    {
				    allPathNum[i][j][k+1] = min(allPathNum[i][j][k], 
					   allPathNum[i][k][k] + allPathNum[k][j][k]);
				    pathM[i][j][k] = allPathNum[i][j][k]>allPathNum[i][k][k]+
					    allPathNum[k][j][k]? 1:0;

			    }
		    }
	    }
	    return allPathNum;
    }
};

测试主程序太大了，所以分开比较好看：

int main()
{
	int a[] = {0, 2, 9};
	vector<int> v(a, a+3);
	vector<vector<int> > vArray;
	vArray.push_back(v);
	v[0] = 8 ;v[1] = 0; v[2] = 6; 
	vArray.push_back(v);
	v[0] = 1 ;v[1] = INT_MAX; v[2] = 0; 
	vArray.push_back(v);
	for(auto x: vArray)
	{
		for(auto y:x)
			cout<<y<<"\t";
		cout<<endl;
	}
	cout<<endl;

	vector<vector<vector<int> > > allPathNum;
	vector<vector<vector<int> > > pass;
	Solution solu;
	allPathNum = solu.FloydAllShortestPath(vArray, pass);

	for(auto x: allPathNum)
	{
		for(auto y:x)
		{
			for(auto z:y)
				cout<<z<<"\t";
			cout<<endl;
		}
		cout<<endl;
	}
	cout<<endl;

	for(int i=0; i< pass.size(); i++)
	{
		for (int j = 0; j < pass[i].size(); j++)
		{
			cout<<"Vector "<<i<<" to "<<j<<" pass:";
			for (int k = 0; k < pass[i][j].size(); k++)
			{
				if(pass[i][j][k] == 1)
					cout<<k<<"\t";
			}
			cout<<endl;
		}
		cout<<endl;
	}

	system("pause");
	return 0;
}

这里是打印了三个矩阵，第一是记录路径的矩阵；

第二个是记录最短路径的矩阵，这是中间那个三维矩阵，第一矩阵表示第一个点到其他三点的最短路径，如第一行是原始的直接从第一点到其他点的距离，中间不经过任何其他点，第二行是指测试了加入第一个点作为中间路径，第三行是指测试了加入第二个点作为中间路径，第四行是指测试了加入第三点作为中间路径；可以看出第一点到第三点的最短路径是经过了第二个点。

其路径如下图：

第三个是计算经过路径的矩阵，如果看第二个三维矩阵不好看，那么这里打印就是为了方便观察的。这里的下标是从0开始。

运行结果：