DFS求旅行商问题

设有城市1.2.3.4，求从1出发，不重复地经过4个城市且最终返回城市1的最短路径
问题分析：
将该题转为加权图模型，尝试所有可行路线，并比较得出最短路径。

#include<iostream>
#define M 10
#define N 10
using namespace std;

int dis[M][N];
int ans =100;
int n;
int a[5];
void create()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {

            int tem;
            cin>>tem;
            dis[i][j]=tem;
            //cin>>mtx[i][j];
            dis[j][i]=dis[i][j];
        }
    }
}
void disp(int n){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<dis[i][j]<<"\t";
        }
        cout<<endl;
    }
}

//搜索的路径为中间三个，头和尾都为城市1 
void dfs(int* a,int len,int num,int u)
//数组记录礼金城市的顺序，len记录总距离，num记录经过城市个数
//u表示当前在那个城市
{
    if(num==n)
    {
        if(dis[u][1]==-1) return;//值为说明此路不通
        len+=dis[u][1];           //否则累加距离
        ans=min(ans,len);         //并将该累加值与最终结果比较
        return;
    }
    for(int i=2;i<=n;i++)       //依次以城市2. 3 .4，为第一站开始搜索
    {
        int flg = 0;
        for(int j=1;j<=num;j++)
        {
            if(a[j]==i)
            {
                flg=1;          //排除已经经过该城市的情况
                break;
            }
        }
        if(!flg && dis[u][i]!=-1)   //该边可以走并且没有走过
        {
            a[num+1] = i;
            dfs(a,len + dis[u][i],num+1,i);//记录该站并继续搜索
        }
    }
}
int main(){
    //freopen("C:\\in.txt","r",stdin);
    //int n;
    cin>>n;
    create();
    disp(n);
    dfs(a,0,1,1);
    for(int i=2;i<=n;i++)
        cout<<a[i]<<"  ";
    cout<<endl;
    cout<<ans;
}
/*
4
-1 4 -1 5
4 -1 -1 7
-1 -1 -1 3
5 7 3 -1

4
-1 5 3 4
5 -1 7 6 
3 7 -1 -1
4 6 -1 -1
*/

复杂度：
O(n!)