思路：
1 用一个矩阵来记录从i到j的最短路径
2 用三层循环，选好一个点k，然后把所有其他点组成两对i和j；测试从i到j是直接走近，还是从i经过k最后到j比较近一点。如果绕道k之后花费更小一点，那么就更新[i][j]的数据。
3 循环完毕就记录了所有两点之间的最短距离了。
看下面的实现程序，用了两个循环，第一循环是赋值给记录最短路径的矩阵，第二个循环就是实际记录最短路径的算法。
用了两个矩阵，第二个矩阵是为了可以打印出来两点之间的最短路径都经过了那些点：
[cpp]
#include
#include
using namespace std;
class Solution {
public:
vector > > FloydAllShortestPath(vector >& matrixGraph,
vector > >& pathM)
{
int n = matrixGraph.size();
vector > > 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;
}
};
测试主程序太大了，所以分开比较好看：
[cpp]
int main()
{
int a[] = {0, 2, 9};
vector v(a, a+3);
vector > 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<
cout<
}
cout<
vector > > allPathNum;
vector > > pass;
Solution solu;
allPathNum = solu.FloydAllShortestPath(vArray, pass);
for(auto x: allPathNum)
{
for(auto y:x)
{
for(auto z:y)
cout<
cout<
}
cout<
}
cout<
for(int i=0; i< pass.size(); i++)
{
for (int j = 0; j < pass[i].size(); j++)
{
cout<<"Vector "<
for (int k = 0; k < pass[i][j].size(); k++)
{
if(pass[i][j][k] == 1)
cout<
}
cout<
}
cout<
}
system("pause");
return 0;
}