Floyd_Warshall算法主要用于求解所有节点对的最短路径，代码如下：
#include<iostream> using namespace std; #define Inf 65536;
#define NIL -1; int N = 5; //假定图的节点有5个
int map[6][6]; //为方便，节点从1开始标号，该矩阵存储权重
int dist[6][6][6];
int path[6][6][6]; void Init() //构建邻接矩阵
{
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
if (i == j)
{
map[i][j] = 0;
}
else
map[i][j] = Inf;
}
}
map[1][2] = 3, map[1][3] = 8, map[1][5] = -4;
map[2][4] = 1, map[2][5] = 7;
map[3][2] = 4;
map[4][1] = 2, map[4][3] = -5;
map[5][4] = 6; } void Floyd_Warshall()
{
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
dist[i][j][0] = map[i][j];
path[i][j][0] = NIL;
}
}
path[1][2][0] = 1, path[1][3][0] = 1, path[1][5][0] = 1;
path[2][4][0] = 2, path[2][5][0] = 2;
path[3][2][0] = 3;
path[4][1][0] = 4, path[4][3][0] = 4;
path[5][4][0] = 5;
for (int k = 1; k <= N; k++)
{
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
if (dist[i][j][k - 1] <= dist[i][k][k - 1] + dist[k][j][k - 1])
{
dist[i][j][k] = dist[i][j][k - 1];
path[i][j][k] = path[i][j][k - 1];
} else
{
dist[i][j][k] = dist[i][k][k - 1] + dist[k][j][k - 1];
path[i][j][k] = path[k][j][k - 1];
} }
}
}
} void Printf_Path(int path[6][6][6], int i, int j)
{
if (i == j)
cout << i << " ";
else if (path[i][j][N] == -1)
{
cout << "NO path from " << i << " to " << j << "exists" << endl;
}
else
{
Printf_Path(path, i, path[i][j][N]);
cout << j << " ";
} } int main()
{
Init();
Floyd_Warshall(); for (int k = 0; k <= N; k++)
{
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
cout << dist[i][j][k] << " ";
}
cout << endl;
}
cout << endl;
} for (int k = 0; k <= N; k++)
{
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
cout << path[i][j][k] << " ";
}
cout << endl;
}
cout << endl;
} Printf_Path( path, 1, 4);
return 0;
}
夜深了，至亲至疏至陌路。