算法基础之最短Hamilton路径

发布时间:2023年12月30日

最短Hamilton路径

  • 核心思想: 数位dp

    • 用二进制数 存当前所有点 遍历过为1

    • 遍历i图中j点 若j点走过 则求j点路径长度

      • f[state][j] = f[state_k][k] + w[k][j] state为除去j点的图
    •   #include<iostream>
        #include<cstring>
        #include<algorithm>
        
        using namespace std;
        const int N = 20, M = 1<< N ;
        
        int f[M][N];
        int w[N][N];  //权值
        int n;
        
        int main()
        {
            cin>>n;
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    cin>>w[i][j];  //输入所有边长度(权值)
                    
            memset(f , 0x3f, sizeof f);  //初始化无穷大 便于取min
            f[1][0] = 0;  //只有起点走过 且当前点为起点 距离为0
            
            for(int i=1;i< 1 << n;i++)  //遍历每一张图
                for(int j=0;j<n;j++)  //遍历i图中每个点
                    if(i >> j & 1)  // 若j点走过
                        for(int k= 0;k<n;k++)  //遍历j点前一个点k
                            if(i >> k & 1)  //k也走过 
                                //更新f[i][j] = f[去掉i][k] +w 
                                //特别地 当j == k时 f[state][k] 不合法 因为图中必须包含k点
                                //所有min只会取f[i][j]
                                f[i][j] = min(f[i][j] , f[i - (1 << j)][k] + w[k][j]);
                                
            cout<< f[(1 << n) - 1][n-1]<<endl;  //输出所有点都走过 当前点为n-1的数值
        }
      
文章来源:https://blog.csdn.net/Pisasama/article/details/135307357
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。