最短路径-Floyd算法

floyd算法用以解决所有点对最短路径。

floyd算法基本思想是递推，动态规划。我们记 dp[i][j][k] 表示图中顶点 i 到 j 的最短路径，且该最短路径中，所经过的中间顶点(不包括 i, j) 的范围为 [1,k]，由此我们可以得到以下递推式：

dp[i][j][k]= w[i][j]   如果 k== 0

dp[i][j][k]= min{ dp[i][k][k-1]+ dp[k][j][k-1] }  如果 k>= 1。

实际中，空间上我们可以减少一维。

 

floyd算法同样可以来解决一些其它问题

1) 有向图的最小(或最大)环

这个问题答案其实就是自身到自身的最短路径，运行完 floyd 后，对每个顶点取自身到自身距离的最小者。

 

2) 无向图的最小环

根据以上的递推式，dp[i][j][k] 表示 i 到 j 的最短路径，且该最短路径中，所经过的中间顶点(不包括 i, j) 的范围为 [1,k]。

此时我们可以枚举出顶点序列最大为 k+ 1 的所有最小环，如何枚举：设与顶点序列最大的顶点 k+ 1 相连的两个顶点为 x, y，x,y 须满足 x, y<= k。这样最小环构成为 边  边 及 x 到 y 的最短路径。

Poj 1734 Sightseeing trip

#include <stdio.h>
#include <stdlib.h>

int const N= 110, inf= 5000000;
int mat[N][N], dist[N][N], pre[N][N], path[N], n, m, top= 0, p;

#define min(a,b) ((a)<(b)?(a):(b))

int main(){
    scanf("%d%d",&n,&m );
    for( int i= 0; i<= n; ++i )
    for( int j= 0; j<= n; ++j ){
        mat[i][j]= inf; dist[i][j]= inf; pre[i][j]= j; }
    while( m-- ){
        int u, v, d;
        scanf("%d%d%d",&u,&v,&d);
        mat[u][v]= min( mat[u][v], d );
        mat[v][u]= mat[u][v];
        dist[u][v]= mat[u][v]; dist[v][u]= mat[v][u];
    }
    int ans= inf;
    for( int k= 1; k<= n; ++k ){
        for( int x= 1; x< k; ++x )
        for( int y= 1; y< x; ++y ){
            if( mat[x][k]+ mat[k][y]+ dist[x][y]< ans ){
                ans= mat[x][k]+ mat[k][y]+ dist[x][y];
                top= 0; path[top++]= k; p= x;
                while( y ){
                    path[top++]= p; p= pre[p][y];
                }
                path[top++]= y;
            }
        }
        for( int i= 1; i<= n; ++i )
        for( int j= 1; j<= n; ++j )
        if( dist[i][k]+ dist[k][j]< dist[i][j] ){
            dist[i][j]= dist[i][k]+ dist[k][j];
            pre[i][j]= pre[i][k]; }
    }
    if( top> 0 ){
        printf("%d", path[0] );
        for( int i= 1; i< top; ++i ) printf(" %d", path[i] );
        puts("");
    }else puts("No solution.");
    
    return 0;
}

3) 带限制的多点对最短路径

TOJ 3214 Find the Path

题意为给一个城市图，每个城市 i 有 ci 个警察，现有两个城市 u 和 v，找一条最短路径使得最短路径上任意一个城市的警察数量不大于 k。解法依然用到了 floyd 算法的思想，回到 dp[i][j][k] 表示图中顶点 i 到 j 的最短路径，且该最短路径中，所经过的中间顶点(不包括 i, j) 的范围为 [1,k] 这个定义，在这个问题中，我们加入中间顶点时按照警察数量从小到大的顺序加入。所以 dp[i][j][k] 所得到的最短路径中，每一个中间顶点的警察数量不会超过顶点 k 的警察数量。

代码

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;
int const N= 205, inf= 2000000;
struct Node{
    int cops, id;
}c[N];
int mat[N][N][N], n, m;

bool operator<(Node a, Node b ){
    return a.cops< b.cops; }
    
int main(){
    int test;
    scanf("%d", &test );
    while( test-- ){
        scanf("%d%d",&n,&m );
        for( int i= 1; i<= n; ++i ){
            scanf("%d", &c[i].cops);
            c[i].id= i; }
        
        sort( c+ 1, c+ 1+ n );
        
        for( int i= 0; i<= n; ++i )
        for( int j= 0; j<= n; ++j )
        mat[i][j][0]= inf;
        
        while( m-- ){
            int u, v, d;
            scanf("%d%d%d",&u,&v,&d );
            u++,v++;
            mat[u][v][0]= d; mat[v][u][0]= d;
        }
        
        for( int k= 1; k<= n; ++k ){
            for( int i= 1; i<= n; ++i )
            for( int j= 1; j<= n; ++j )
            mat[i][j][k]= mat[i][j][k-1];
            
            for( int i= 1; i<= n; ++i )
            for( int j= 1; j<= n; ++j ){
                int p= c[k].id;
                if( mat[i][p][k-1]+ mat[p][j][k-1]< mat[i][j][k] )
                mat[i][j][k]= mat[i][p][k-1]+ mat[p][j][k-1];
            }
        }
        int q;
        scanf("%d",&q );
        while( q-- ){
            int u, v, k;
            scanf("%d%d%d",&u,&v,&k );
            u++, v++;
            
            int i= 1;
            while( i<= n && c[i].cops<= k ) i++; i--;
            
            if( mat[u][v][i]!= inf ) printf("%d\n", mat[u][v][i] );
            else puts("-1");
        }
        puts("");
    }
    return 0;
}

4) floyd 与有向图的连通性

有向图的传递闭包可以用 floyd 算法求出。

ZOJ 3232 It's not Floyd Algorithm

题意为给出一个已经做过传递闭包的矩阵，求出原图最少由多少边组成。

先考虑原图与做过传递闭包后的新图的关系：对于原图中的强连通分量，做过传递闭包后，强连通分量就变成了团，任意两点都有边，所以新图中求得强连通分量一定是一个团，对于团，一定可以找到一个环把所有顶点连起来。可以证明，对于新图中的有 n(n>1) 个顶点的强连通分量，原图中至少需要 n 条边才能构成，只要取一个环就行了。把所有强连通分量处理后，这时的新图就了一个有向无环，这时我们可以做反闭包，求出剩余图所需的边数。

代码：

#include <stdio.h>
#include <stdlib.h>

int const N= 210;
int n, mat[N][N], map[N][N];
int dep[N], low[N], mark[N], stack[N], cnt, top, c, num[N];

void dfs( int u ){
    dep[u]= ++cnt; low[u]= dep[u]; stack[++top]= u;
    for( int v= 1; v<= n; ++v )
    if( mat[u][v] ){
        if( dep[v]== 0 ) {
            dfs( v );
            if( low[v]< low[u] ) low[u]= low[v];
        }
        else if( low[v]!= n && dep[v]< low[u] ) low[u]= dep[v];
    }
    if( dep[u]== low[u] ){
        c++;
        do{
            int v= stack[top];
            mark[v]= c; low[v]= n;
        }while( stack[top--]!= u );
    }
}

int main(){
    while( scanf("%d",&n)!= EOF ){
        for( int i= 0; i<= n; ++i )
        for( int j= 0; j<= n; ++j ) {
            mat[i][j]= 0; map[i][j]= 0; }
        
        for( int i= 1; i<= n; ++i )
        for( int j= 1; j<= n; ++j )
        scanf("%d", &mat[i][j] );