旅行商问题【回溯】（C语言）

给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

可以看出abcdea这条线路是最短的。
我们把abcde抽象为12345进行算法设计。有两种思路：固定起点和不固定起点。

代码

#include 
#include 
#define MAXSIZE 10
#define FINITY 1000
int thingnum; //节点数
int bian;//边个数
int a[MAXSIZE][MAXSIZE];//邻接矩阵
int x[MAXSIZE]={0,3,2,5,1,4};


int cc=0;
int bestc=FINITY;
int bestx[MAXSIZE];
//输出邻接矩阵
void outputjuzhen()
{
    int i,j;
    for(i=1;i<=thingnum;i++)
    {
        for(j=1;j<=thingnum;j++)
        {
            printf("%-5d",a[i][j]);
        }
        printf("n");
    }
}
//交换
void swap(int t,int i)
{
    int temp;
    temp = x[t];
    x[t] = x[i];
    x[i] = temp;
}

void bactrack(int i)
{
    int j,k;
    if(i==thingnum)
    {
        if(a[x[thingnum-1]][x[thingnum]]!=FINITY && a[x[thingnum]][x[1]]!=FINITY && (cc+a[x[thingnum-1]][x[thingnum]]+a[x[thingnum]][x[1]] < bestc || bestc ==FINITY))
        {
            for(j=1;j<=thingnum;j++)
            {
                bestx[j] = x[j];
            }
            bestc = cc+a[x[thingnum-1]][x[thingnum]]+a[x[thingnum]][x[1]];

        }
    }
    else
    {
        for(int j=i;j<=thingnum;j++)
        {
            if(a[x[i-1]][x[j]]!=FINITY && (cc+a[x[i-1]][x[j]] 
 
不固定起点 
代码
 
#include 
#include 
#define MAXSIZE 10
#define FINITY 1000
int thingnum; //节点数
int bian;//边个数
int a[MAXSIZE][MAXSIZE];//邻接矩阵
int x[MAXSIZE]={0,3,2,5,1,4};


int cc=0;
int bestc=FINITY;
int bestx[MAXSIZE];
//输出邻接矩阵
void outputjuzhen()
{
    int i,j;
    for(i=1;i<=thingnum;i++)
    {
        for(j=1;j<=thingnum;j++)
        {
            printf("%-5d",a[i][j]);
        }
        printf("n");
    }
}
//交换
void swap(int t,int i)
{
    int temp;
    temp = x[t];
    x[t] = x[i];
    x[i] = temp;
}

void bactrack(int i)
{
    int j,k;
    if(i==thingnum)
    {
        if(a[x[thingnum-1]][x[thingnum]]!=FINITY && a[x[thingnum]][x[1]]!=FINITY && (cc+a[x[thingnum-1]][x[thingnum]]+a[x[thingnum]][x[1]] <= bestc || bestc ==FINITY))
        {
            for(j=1;j<=thingnum;j++)
            {
                bestx[j] = x[j];
            }
            //printf("na[x[thingnum-1]][x[thingnum]]:%d",a[x[thingnum-1]][x[thingnum]]);
            //printf("na[x[thingnum]][1]:%d",a[x[thingnum]][x[1]]);
            bestc = cc+a[x[thingnum-1]][x[thingnum]]+a[x[thingnum]][x[1]];
            printf("nbestx[MAXSIZE]:");
            for(i=1;i<=thingnum;i++)
            {
                printf("%-5d",bestx[i]);
            }
            printf("%-5d",bestx[1]);
            printf("nbestc:%d",bestc);

        }
    }
    else
    {
        for(int j=i;j<=thingnum;j++)
        {
            if(i==1)
            {
                swap(i,j);
                bactrack(i+1);
                swap(i,j);
            }
            else
            {
                if(a[x[i-1]][x[j]]!=FINITY && (cc+a[x[i-1]][x[j]]