弗洛伊德算法解析

弗洛伊德算法是求解图的多源最短路径的。具有重叠子问题结构为：

 

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。

Floyd-Warshall算法的时间复杂度为O(N³)，空间复杂度为O(N²)。

原理： 

Floyd-Warshall算法的原理是动态规划。

设D_i,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。

1. 若最短路径经过点k，则D_i,j,k = D_{i,k,k − 1} + D_{k,j,k − 1}；
2. 若最短路径不经过点k，则D_i,j,k = D_{i,j,k − 1}。

因此，D_i,j,k = min(D_{i,k,k − 1} + D_{k,j,k − 1},D_{i,j,k − 1})。

算法描述：

for k ← 1 to n do
  for i ← 1 to n do
    for j ← 1 to n do
      if (Di,k + Dk,j < Di,j) then
        Di,j ← Di,k + Dk,j; 

案例：

亲测代码：

<span style="font-size:14px;">#include<stdio.h>
#include<string.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
#define maxSize 10
#define INF 1000000
typedef struct 
{
int edges[maxSize][maxSize];
int n;//顶点数 
int e;//边数 
}MGraph;
void fylod(MGraph g , int A[][maxSize], int path[][maxSize])
{
int i,j,k;
for(i=0;i<g.n;i++)
{
for(j=0;j<g.n;j++)
{
A[i][j]=g.edges[i][j];
path[i][j] = -1;
}
}
for(k=0;k<g.n;k++)
{
for(i=0;i<g.n;i++)
{
for(j=0;j<g.n;j++)
{
if(A[i][j]>A[i][k]+A[k][i])
{
A[i][j] = A[i][k]+A[k][j];
path[i][j]=k;
}
}
}
}
}
void printPath(int u,int v ,int path[][maxSize])
{
if(path[u][v]==-1)
{
printf("-->%d",v);
} 
else
{
int mid = path[u][v];
printPath(u,mid,path);//处理他们之间的中间节点 
printPath(mid,v,path);//处理他们之间的中间节点 
}
}
int main()
{
MGraph G;
int A[maxSize][maxSize];
int path[maxSize][maxSize];
int a,b,s;
G.n = 4;
G.e = 8; 
for(int j=0;j<G.n;j++)
{
for(int i=0;i<G.n;i++)
{
G.edges[i][j] = INF;
G.edges[j][i] = INF;
}
}
for(int i=0;i<G.e;i++)
{
scanf("%d%d%d",&a,&b,&s);
G.edges[a][b]=s;
}
fylod(G,A,path);
printf("1-0的最短路径长度为：%d\n",A[1][0]);
printf("经过的路径为：1"); 
printPath(1,0,path); 
return 0;
}</span>

结果：

时间复杂度：

有算法代码可知，本算法的主要部分是一个三重循环，去内层循环的操作为基操作，则基操作执行的次数为n*n*n,因此时间复杂度为O(n3);