the shortest path floyd

Floyd,I think it’s one of the most simple and beautiful algorithm in graph thoery,it only has four lines,but it has a very abundant background.

Floyd takes the dynamic programming solution to solve the shortest path problem.Let’s make

$dp[i][j][k]:$ the shortest path which only use point set {1…k} from point i to point j.

$dp[i][j][k]=min(dp[i][j][k-1],dp[i][k][k-1]+dp[k][j][k-1]])$

the above equation means that we can take out the point k,there will be two ways: whether pass the point k.

if we don’t pass through it,the $dp[i][j][k]=dp[i][j][k-1]$,otherwise,

there will be two steps,step 1,from point i to point k,and step 2,from point k to point j. that’s to say $dp[i][k][k-1]+dp[k][j][k-1]$ .

But the above equation will consume a lot of memory,consider that the stage k only concerned with stage k-1,hence we can use the sliding array.

1
2
3
4
5
6
7

//if have a path from a to b with cost c ,dp[a][b]=c;
//else dp[a][b]=INF;
for(int k=1;k<=n;++k)
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);

notice: You should never put k in the second or third loop,because the k stands for the stage.