'I am trying to write a simple tsp question but meet some problems

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define max 100
void tsp(int Dis[max][max],int v[],int N,int count,int currPos,int cost,int ans){
    /*for(j=1;j<N+1;j++){
        if(visited[j]==0){
            sum+=Dis[i][j];
            visited[j] = 1;
            DFS(visited,j,Dis,sum);
        }
    }*/
    if(count == N&&Dis[1][currPos]>0){
        if(ans> cost+Dis[1][currPos]) ans = cost+Dis[1][currPos];
        //ans = min(ans,cost + Dis[1][currPos]);
        return;
    }

    for (int i = 0;i<N+1;i++){
        if(v[i]==0&&Dis[currPos][i]>0){
            v[i] = 1;
            tsp(Dis,v,N,count + 1,cost + Dis[currPos][i],ans);

            v[i] = 0;
        }
    }
};
int main(int argc, char const *argv[])
{
    int N;
    int size = 1;
    int count = 1;
    char x[100] = {0};
    FILE *fp=fopen(argv[1],"r");
    if(fp==NULL){
        printf("Cannot open the file,strike any key to exit!\n");
        getchar();
        exit(0);
    }
    for (int i = 0;!feof(fp);i++){
        fscanf(fp,"%hhd",&x[i]);
    }
    N=x[0];
    int Dis[N][N], City[N];
    for(int i=1;i<N;i++){
        size=size*i;
    }
    char y[size];
    for (int i=1;i<size+1;i++){
        y[i] = x[i];
        //printf("%d\n",y[i]);
    }
    
    for(int i=2; i < N + 1; i++){
        for(int j=1; j < i ; j++){
            Dis[j][i] = y[count];
            Dis[i][j] = y[count];
            count+=1;
            printf("(%d,%d),(%d,%d)",j,i,i,j);
            printf("%d\n",Dis[j][i]);
        }
        
    }
    for(int i=0;i<N;i++){
        City[i]=i + 1;//create the number of city with 1 ...... N
    }
    int curr_constraint = 0;
    int v[N+1];
    for (int i = 1; i < N+1; i++){
            v[i] = 0;
    }
    for(int i = 1;i<N+1;i++){
        curr_constraint += Dis[i][i+1];
    }
    v[1]= 1;
    int ans = INT_MAX;
    printf("The orginal constraint is %d\n",curr_constraint);
    tsp(Dis[N][N],v,N,0,1,0,ans);
    return 0;
}

The question asks me to implement a tsp question which always starts with the number 1 city, it will read the data including the numbers of nodes and length between two citys from a txt file in the position of argv[1]. And then find the smallest way for all city without going back the first city.

The file is like following:

4
5
40 9
11 6 8

which means:

  • the number of citys N = 4
  • Distance: d[1][2] = 5, d[1][3] = 40, d[2][3] = 9, d[1][4] = 11, d[2][4] = 6, d[3][4] = 8.

I want to create a array including the distance in tsp function, but the lenght I read only in the main function. How to solve this problem?

c


Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source