Floyd算法本质上是一种动态规划
先定义两个二维数组D[x][x],P[x][x], D 代表顶点到定点之间最短路径权值和的矩阵,P代表对应顶点最短路径的前驱矩阵。
先将D初始化为图的邻接矩阵。
其实就是中转点的问题。
动归方程:
D[v][w] = min{ D[v][w], D[v][k]+D[k][w]};
typedef int Pathmtirx[maxv][maxv];
typedef int ShrotPathTable[maxv][maxv];]
//求网图G中各顶点v到其余顶点w的最短路径P[v][w]和带权长度D[v][w]
void ShortestPath_Floyd(MGraph G,Pathmatirx *P,ShortPathTable *D)
{
for(int v = 0; v < G.numVertexes; ++v )
{
for( int w = 0; w < G.numVertexes; ++w)
{
(*D)[v][w] = G.matirx[v][w]; //D[v][w]值即为对应点间的权值
(*P)[v][w] = w; //初始化P
}
}
for(int k = 0; k < G.numVertexes; ++k)
{
for(int v = 0; v < G.numVertexes; ++v)
{
for(int w = 0; w < G.numVertrexes; ++w)
{
if((*D)[v][w] > (*D)[v][k] + (*D)[k][w])
//如果经过下标为k的顶点的路径比原两点路径短
{
(*D)[v][w] = (*D)[v][k] + (*D)[k][w];
(*P)[v][w] = (*D)[v][k];
//路径设置为经过k的顶点
}
}
}
}
}