最短路径问题

一、题目要求：

二、子问题（1）哈密顿回路

1.问题建模描述

给定一个n个结点，m条有向边（边权为正）的图，求出一条路径满足如下条件：

条件一：该路径可以从任意节点开始，不过起点和终点必须相同。

条件二：该路径除了起点和终点，其他结点都必须经过，且只能经过一次。

条件三：在满足上述两条件的前提下，要求路径尽可能短。

2.DFS搜索算法

分析：

有两种搜索的思路，第一种就是在不考虑图的结构的前提下，枚举每一种可能的路径，这样的路径也就是 $n$n个点的全排列，即 $n!$n!种路径。之后对于枚举出来的路径，在根据具体的图的结构，判断其是否可行（是否确实连通），是否为最短路径。第一种时间复杂度显然就是：枚举出来的不同路径数*判断一条路径需要的时间，即： $O(n!\ast n)$O(n!∗n)。

第一种方法的缺点就是没有非常有效的利用图的结构对搜索进行剪枝。所以我们想到第二种方法：对于每个节点，均枚举以它为起点的所有长度为n且每个节点只走一次的合法路径，同时维护当前路径总长度。这样我就不会枚举多余的不存在图中的边，此时如果图是完全图（ $n$n个点， $n\ast n$n∗n条边），那么时间复杂度依然是 $O(n!)$O(n!)，但是对于稀疏图，此方法将极大地减少实际搜索量。

代码：

#include<bits/stdc++.h>
#define xcx(x) printf("ojbk %d\n",x);
using namespace std ;
const int maxn = 100 ; // 最大点数
const int maxm = maxn*maxn ; // 最大边数
const int inf = 0x3f3f3f3f ; // 假装无穷大
struct point{ // 结点
    int t, val ;
    point() {}
    point( int t , int val ) {
        this->t = t ;
        this->val = val ;
    }
};
int n, m, dis[maxn][maxn] ; // n个点，m条边，dis[i][j]是i点到j点的距离
vector<point>u[maxn] ; // 每个点的出边
bool vis[maxn] ; // 标记每个点是否到过
int seq[maxn], best_seq[maxn] ; // seq当前路径结点序列，best_seq最短路径的结点序列
int best_ans ; // 最短距离
void dfs( int s , int len , int  sum ) { // 从s号点出发，走过了len个结点，当前总长为sum
    if ( sum > best_ans ) { // 剪枝：已经不可能找到更短的了
        return ;
    }
    if ( len == n ) { // 遍历完所有结点
        if ( sum + dis[seq[n-1]][s] < best_ans ) { // 更新最短路径
            for (int i=0; i<n; i++) {
                best_seq[i] = seq[i] ;
            }
            best_ans = sum + dis[seq[n-1]][s] ;
        }
        return ;
    }
    int now = seq[len-1] ; // 当前所在结点
    for (int i=0; i<u[now].size(); i++) { // 枚举当前点的所有出边，走第i条出边
        seq[len] = u[now][i].t ;
        vis[seq[len]] = 1 ;
        dfs( s , len+1 , sum+u[now][i].val ) ;
        vis[seq[len]] = 0 ;
    }
}
void Init() { // 初始化
    for (int i=0; i<maxn; i++) {
        u[i].clear() ;
    }
    memset( vis, 0, sizeof(vis) ) ;
    for (int i=0; i<maxn; i++) { // 初始化距离
        for (int j=0; j<maxn; j++) {
            dis[i][j] = inf ;
        }
    }
    best_ans = inf ;
}
void InPut() { // 输入
    scanf( "%d%d", &n, &m ) ; // 假设结点标号从1开始
    for (int i=0; i<m; i++) {
        int temp_s, temp_t, temp_v ;
        scanf( "%d%d%d", &temp_s, &temp_t, &temp_v) ;
        u[temp_s].push_back( point(temp_t,temp_v) ) ;
        dis[temp_s][temp_t] = min( dis[temp_s][temp_t] , temp_v ) ;
    }
}
int main(){
    Init() ;
    InPut() ;
    for (int i=1; i<=n; i++ ) { // 枚举每个起点的哈密顿回路
        memset(vis, 0, sizeof(vis) ) ;
        vis[i] = 1 ;    seq[0] = i ; // 从i号点出发
        dfs(i,1,0) ;
        vis[i] = 0 ;
    }
    if ( best_ans == inf ) { // 不存在哈密顿回路
        printf( "Not exist \n" ) ;
        return 0;
    }
    /// 输出最短路径
    printf( "shortest way length : %d\n", best_ans ) ;
    printf( "sequence :" ) ;
    for (int i=0; i<n; i++ ) {
        printf( "%d --> ", best_seq[i] ) ;
    }
    printf( "%d\n", best_seq[0] ) ;

    return 0;
}

3.动态规划算法（状压dp+记录路径）

状态定义：

$dp(s,t,state)表示从s号点出发，到达t号点，当前路径状态为state需要的最短距离是多少$dp(s,t,state)表示从s号点出发，到达t号点，当前路径状态为state需要的最短距离是多少。
这里解释一下什么是什么路径状态：
首先，我们从某一个点 $s$s出发，走到了一个点 $t$t，那么我如何知道我之前经过了哪些点呢，最简单的办法当然就是开一个数组记录下来了，不过这样还是有一些浪费空间的。所以我们就想到这样一个办法：用 $0$0表示没到过，用 $1$1表示到过，这样一个长度为 $n$n的 $01$01序列，就能表示这 $n$n个点我分别有没有到过了，那么这个长度为 $n$n的 $01$01序列，恰好就可以看成是一个二进制数字，那么我们就可以把它当成数组的下标储存起来了，这个二进制数字，就是 $state$state也就是路径状态。我们还可以更形象的举个栗子：比如 $state=14$state=14，那么它表示成 $2$2进制就是： $1110$1110，就表示到过的结点的标号为： $1,2,3$1,2,3，没到过的结点的标号为： $0$0。

状态转移方程：

$dp(s,t,state)=\max \left\{dp\right(s,k,state-(1\&lt;\&lt;t))+dis(k,t\left)\right\}$dp(s,t,state)=max{dp(s,k,state−(1<<t))+dis(k,t)}
注： $dis(k,t)$dis(k,t)表示点t到点k的边长（若 $k$k点和 $t$t点不直接相连则为无穷大）
注意这里还有一些要求：
1.首先就是状态 $dp(s,t,state)$dp(s,t,state)的合法性，也就是 $state$state表示的状态中，点 $s$s和 $t$t必须被标记为已经走过，即： $state\mathrm{\&amp;}(1\&lt;\&lt;s)==1$state&(1<<s)==1 且 $state\mathrm{\&amp;}(1\&lt;\&lt;t)==1$state&(1<<t)==1。
2.为了保证能从 $k$k点走到 $t$t点，那么 $dis(k,t)$dis(k,t)一定不能等于 $inf$inf（无穷大），或者说，一定存在点 $k$k到点 $t$t的直接连边。
3.为了可以保证每个点只能路过一次，那么 $state$state状态中， $k$k点一定要被标记为走过，即： $state\mathrm{\&amp;}(1\&lt;\&lt;k)==1$state&(1<<k)==1。

状态边界：

显然从任何点开始并且站在这个点上都是合法的，即： $dp(s,s,1\&lt;\&lt;s)=0$dp(s,s,1<<s)=0

递归结构：

那么有了上面的分析，我们就知道了一定可以通过某种方式计算出最终的答案： $max\left\{dp\right(i,j,1\&lt;\&lt;\left(n\right)-1)+dis(j,i)\mid i!=j且0\le i\le n-1且0\le j\le n-1\}$max{dp(i,j,1<<(n)−1)+dis(j,i)∣i!=j且0≤ i≤n−1且0≤j≤n−1}
现在我们的任务就是需要根据初始状态和状态转移方程将每一种需要用到的状态dp值计算出来。其实我对于每个合法状态： $dp(s,t,state)$dp(s,t,state)，只需要枚举所有终点是 $t$t的有向边就好了。我们只需使用一个递归函数计算就可以了（需要记忆化 $dp$dp 数组）。

记录路径：

但是我们非常遗憾的发现了一个问题，这样做我们虽然能得到我们最终的最短路径长度，但是我们没有得到这个最短的路径具体的结点序列是多少。其实我们只需要再开一个对应的数组 $pre(s,t,state)$pre(s,t,state)表示到达状态 $dp(s,t,state)$dp(s,t,state)的最短路径上一次走的是哪一个点，这样我们就可以根据这个 $pre$pre数组返向找回去，得到最短的路径结点序列了！

时间复杂度分析：

状态数量为： $n\ast n\ast 2^n$n∗n∗2n，其中对于每个状态，我需要枚举这个状态对应当前所在终点的所有出边，来将它的值转移到下一个状态，最差情况下（完全图），每个状态枚举的终点的出边的数量就是 $n$n，然后每次对于确定的状态和确定的出边，就需要 $O\left(1\right)$O(1)的时间就可以将它递推到下一个状态。所以最差的时间复杂度为： $O(n^3\ast 2^n)$O(n3∗2n)。当然，我们还可以继续具体一下这个时间，我们单独考虑每条边，那么每条边被作为出边的次数为 $n\ast 2^n$n∗2n次（ $n$n是起点数量， $2^n$2n是状态数量），所以其实准确的时间复杂度为： $O(n^2\ast 2^n+n\ast m\ast 2^n)$O(n2∗2n+n∗m∗2n)

代码：

#include<bits/stdc++.h>
#define xcx(x) printf("ojbk %d\n",x);
using namespace std ;
const int maxn = 10 ; // 最大点数
const int maxm = maxn*maxn ; // 最大边数
const int inf = 0x3f3f3f3f ; // 假装无穷大
struct point{ // 结点
    int s, val ; // 起点为s，边权为val的边
    point() {}
    point( int s , int val ) {
        this->s = s ;
        this->val = val ;
    }
};
int n, m, dis[maxn][maxn] ; // n个点，m条边，dis[i][j]是i点到j点的距离
vector<point>u[maxn] ; // 每个点的出边
int dp[maxn][maxn][1<<maxn], pre[maxn][maxn][1<<maxn] ;

void Init() { // 初始化
    for (int i=0; i<maxn; i++) {
        u[i].clear() ;
    }
    for (int i=0; i<maxn; i++) { // 初始化距离
        for (int j=0; j<maxn; j++) {
            dis[i][j] = inf ;
        }
    }
    for (int i=0; i<maxn; i++) { // 初始化dp,pre
        for (int j=0; j<maxn; j++) {
            for (int k=0; k<(1<<maxn); k++) {
                dp[i][j][k] = -1 ; // 表示位计算出对应状态的dp值
                pre[i][j][k] = -1 ;
            }
        }
        dp[i][i][1<<i] = 0 ; // 边界
    }
}
void InPut() { // 输入
    scanf( "%d%d", &n, &m ) ; // 假设结点标号从1开始
    for (int i=0; i<m; i++) {
        int temp_s, temp_t, temp_v ;
        scanf( "%d%d%d", &temp_s, &temp_t, &temp_v) ; // 将输入结点标号变成从0开始
        temp_s-- ;
        temp_t-- ;
        u[temp_t].push_back( point(temp_s,temp_v) ) ; // 存返向边
        dis[temp_s][temp_t] = min( dis[temp_s][temp_t] , temp_v ) ;
    }
}
int CalDp( int s , int t , int state ) { // 计算dp数组
    if ( dp[s][t][state] != -1 ) return dp[s][t][state] ;
    if ( (state&(1<<s))==0 || (state&(1<<t))==0 ) return dp[s][t][state] = inf ; // 不合法状态
    int ret = inf ; // 最优答案
    int best_k = -1 ;
    for (int k=0; k<u[t].size(); k++) { // 枚举每一条终点为t的边
        int p = u[t][k].s ; // 尝试递归，边 p-->t
        if ( (state&(1<<p)) == 0 ) continue ; // 不可能由边p转移到
        CalDp( s , p , state-(1<<t) ) ;// 提前计算好前一状态
        if ( dp[s][p][state-(1<<t)] == inf ) continue ; // 不合法
        if ( best_k == -1 || dp[s][p][state-(1<<t)]+dis[p][t] < ret ) { // 更新
            best_k = p ;
            ret = dp[s][p][state-(1<<t)]+dis[p][t] ;
        }
    }
    pre[s][t][state] = best_k ;
    return dp[s][t][state] = ret ;
}

int main(){
    Init() ;
    InPut() ;

    ///计算dp数组
    int best_ans = inf, best_i, best_j, best_seq[maxn] ;
    for (int i=0; i<n; i++) { // 枚举每一个点为起点的哈密顿回路
        for (int j=i+1; j<n; j++) {
            int temp = CalDp( i, j, (1<<n)-1 ) + dis[j][i] ;
            if ( temp < best_ans ) {
                best_ans = temp ;
                best_i = i ;
                best_j = j ;
            }
        }
    }

    ///根据pre数组，返向找到最短路径
    int now = n-1, now_state = (1<<n)-1 ;
    best_seq[now] = best_j ;    now--;
    while ( best_i != best_j ) {
        best_seq[now] = pre[best_i][best_j][now_state] ;
        now_state-= 1<<best_j ;
        best_j = best_seq[now] ;
        now--;
    }

    /// 输出最短路径
    if ( best_ans == inf ) { // 不存在哈密顿回路
        printf( "Not exist \n" ) ;
        return 0;
    }
    printf( "shortest way length : %d\n", best_ans ) ;
    printf( "sequence :" ) ;
    for (int i=0; i<n; i++ ) {
        printf( "%d --> ", best_seq[i]+1 ) ;
    }
    printf( "%d\n", best_seq[0]+1 ) ;

    return 0;
}

进一步优化：

因为路径最后会形成一个环状结构，所以任意一条路径一定可以表示成从 $1$1号结点开始的路径，所以，我们只需要固定起点是 $1$1号结点，然后再计算就可以了，这样时间复杂度又会降低 $n$n倍，即为： $O(n\ast 2^n+m\ast 2^n)$O(n∗2n+m∗2n)。

三、子问题（2）动态规划求解最短路径

1.问题建模描述

给定一个 $n$n个结点， $m$m条无向边（边权为正）的图，求出某两个给定点 $（s，t）$（s，t）之间的最短路径。

2.floyd算法（动态规划算法）

首先可以去百度一下floyd算法是什么，然后我们下面说一下问什么floyd算法也可以看成是动态规划。

状态定义:

$dp(i,j,k)$dp(i,j,k)表示从 $i$i点到 $j$j点，经过标号在 $[1,k]$[1,k]的所有点松弛之后得到的最短路长度为多少。
这里说明一下什么叫松弛：假如存在三个点 $a,b,c$a,b,c他们之间的距离为： $dis(a,b)=18，dis(a,c)=2，dis(c,b)=3$dis(a,b)=18，dis(a,c)=2，dis(c,b)=3。那么我们就可以发现，在从 $a$a点到 $b$b点的过程中，如果经过 $c$c点，可以减少距离，那么这种情况就叫做 $c$c松弛了 $a$a到 $b$b之间的路径。

状态转移：

$dp(i,j,k)=min\left\{dp\right(i,j,k-1),dp(i,k,k-1)+dp(k,j,k-1\left)\right\}$dp(i,j,k)=min{dp(i,j,k−1),dp(i,k,k−1)+dp(k,j,k−1)}
这也就是用 $k$k松弛 $i$i到 $j$j之间的距离。

初始状态：

$dp(i,j,0)=dis(i,j)$dp(i,j,0)=dis(i,j)

记录路径：

还是同样的问题，我们只知道最短是多少，我们还需要知道最短的路径实际是什么，那么怎么办呢，就是还需要 $pre$pre数组记录动态规划过程中的转移路径， $pre(i,j,k)$pre(i,j,k)表示 $dp(i,j,k)$dp(i,j,k)是否是由 $dp(i,j,k-1)$dp(i,j,k−1)转移过来的。这样我根据 $pre$pre数组返向找回去就知道每一个点是否松弛了i到j的距离，也就知道了最短路径。此处可能需要用到递归。

总结：

这样就可以把floyd算法的三层 for 循环看成是状态的转移，也就解释了为什么松弛点的循环在最外层。同时，我们仔细观察状态转移方程的结构，就可以发现，我们完全可以将dp数组的第三维压缩掉，循环利用即可。

代码：

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 105 ;
    const int inf = 0x3f3f3f3f ;
    int n, m, dis[maxn][maxn] ;
    int pre[maxn][maxn][maxn], dp[maxn][maxn][maxn];
    struct Way{ // 路径
        int s, t, w ;
        vector < int > seq ;
        Way( int s , int t , int w ) {
            this->s = s ;
            this->t = t ;
            this->w = w ;
            seq.clear();
        }
        void print() {
            printf( "dis(%d,%d)=%d\nway: ", s, t, w ) ;
            for (int i=0; i<seq.size(); i++) {
                printf( "%d", seq[i] ) ;
                if ( i!=seq.size()-1 ) printf( "-->" ) ;
            }
            printf( "\n" );
        }
    };
    
    Way operator + ( Way l , Way r ) { // 链接路径l,r
        Way ret = Way( l.s , r.t , l.w+r.w ) ;
        for (int i=0; i<l.seq.size(); i++) {
            ret.seq.push_back( l.seq[i] ) ;
        }
        for (int i=1; i<r.seq.size(); i++) {
            ret.seq.push_back( r.seq[i] ) ;
        }
        return ret ;
    }
    
    Way getWay( int st , int ed , int k ) { // 计算st到ed的路径
        if ( k == 0 ) { // 没有其它点可以松弛
            Way ret = Way( st , ed , dp[st][ed][k] ) ;
            ret.seq.push_back(st) ;
            if ( st != ed ) ret.seq.push_back(ed) ;
            return ret ;
        }
        if ( pre[st][ed][k] == 1 ) { // k松弛了st到ed的距离
            return getWay( st , k , k-1 ) + getWay( k , ed , k-1 ) ;
        }
        else { // k没有松弛st到ed的距离
            return getWay( st , ed , k-1 ) ;
        }
    }
    int main(){
        scanf( "%d%d", &n, &m ) ;
        for (int i=0; i<maxn; i++) {
            for (int j=0; j<maxn; j++) {
                if ( i == j ) dis[i][j] = 0 ;
                else dis[i][j] = inf ;
            }
        }
        for (int i=0; i<m; i++) {
            int s, t, w ;
            scanf( "%d%d%d", &s, &t, &w ) ;
            dis[s][t] = dis[t][s] = w ;
        }
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                dp[i][j][0] = dis[i][j] ;
            }
        }
        for (int k=1; k<=n; k++) {
            for (int i=1; i<=n; i++) {
                for (int j=1; j<=n; j++) {
                    if ( dp[i][j][k-1] < dp[i][k][k-1]+dp[k][j][k-1] ) {
                        dp[i][j][k] = dp[i][j][k-1] ;
                        pre[i][j][k] = 0 ;
                    }
                    else {
                        dp[i][j][k] = dp[i][k][k-1]+dp[k][j][k-1] ;
                        pre[i][j][k] = 1 ;
                    }
                }
            }
        }
        int st, ed ;
        while( scanf( "%d%d", &st, &ed ) != EOF ) {
            Way ans = getWay( st , ed , n ) ;
            ans.print() ;
        }
    
        return 0;
    }
    /* 11 17 1 2 12 1 3 12 2 4 6 2 5 11 3 4 3 3 7 9 4 6 5 5 6 9 5 8 10 6 7 6 6 9 12 7 10 11 8 9 9 8 11 7 9 10 9 9 11 10 10 11 10 1 10 */