Floyd算法——最短路径
弗洛伊德算法（Floyed）
Floyd算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。
Floydl算法的时间复杂度为O(N3)，空间复杂度为O(N2)。
Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）
从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。
2).算法描述：
a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
首先从简单的例子入手
从复杂的图入手，首先画出D[]和P[]数组。
typedef int Pathmatirx[max][max];
typedef int ShortPathTable[max][max];
//求网图G中各顶点V到其余顶点u最短路径P[V][W]及带权长度D[v][w]
void shortPath_Floyd(MGraph G, Pathmatirx *p, ShortPathTable *d)
{
int v,w,k;
//初始化D和P
for(v=0;v<G.numVertex;v++)
{
for(w=0;v<G.numVertex;w++)
{
(*D)[v][w]=G.matirx[v][w]; //D[v][w]值为对应点间的权值
(*p)[v][w]=w; //初始化P
}
}
for(k=0;k<G.numVertexl;k++) //表示中转顶点
{
for(v=0;v<G.numVertex;v++) //v表示起始起点
{
for(w=0;v<G.numVertex;w++) //w表示结束顶点
{
if( (*D)[v][w] > (*D)[v][k] +(*D)[k][w] )
{
/*如果经过下标为K顶点路径比原两点间路径更短
将当前两个间权值设为更小的一个 */
(*D)[v][w] =(*D)[v][k] + （*D）[k][w];
(*p)[v][w] =(*p)[v][k]; //路径设置经过下标为K的顶点
}
}
}
}
}分析：
当k=0时，也就是所有顶点都经过v0中转，计算是否有最短路径的变化，可惜结果没有。
当k=1时，也就是所有顶点都经过v1中转。此时当v=0时，原来D[0][2]=5，现在由于D[0][1][+D[1][2]=4。两个取其最小值，得到D[0][2]=4。同理可得D[]1[3]=8、D[0][4]=6，当v=2、3、4时，也修改了一些数据，如图所示。由于这些最小权值的修改，所以在路径矩阵P上，也要做处理，将他都改为当前的P[V][K]值。
如何从P这个路径数组得出具体的最短路径呢？
以V0到V8为例，P[0][8]=1，得到要经过顶点V1，然后将1取代0得到P[1][8]=2,说明要经过V2,然后将2取代1得到P[2][8]=3,说明要经过V3,.....这样很容易得出最终的路径值v0->v1->v2->v4->v3->v6->v7->v8
求最短路径的显示代码
for(v=0;v<G.numVertex;v++)
{
for(w=v+1;w<G.numVertex;w++)
{
cout<<v<<" weight:"<<D[v][w];
k=P[v][w];
cout<<"Path : "<<v;
while(K!=w)
{
cout<<" -> "<<k; //打印路径顶点
k=P[k][w];
}
cout<<" -> "<<w<<endl; //打印终点
}
cout<<endl;
}Floyed算法他的代码非常简单，就是一个二重循环初始化夹一个三重循环权值修正，就完成了所顶点到所有顶点的最短路径计算。所以当你需要求所有顶点的最短路径问题时，Floyed算法是个不错的选择。