Uncategorized

Traveling salesman problem using dynamic method

#include<stdio.h>

int a[10][10],visited[10],n,cost=0;

int tsp(int c)

{

int cnt, near_city = 999;

int min = 999, temp;

for(cnt = 0; cnt < n; cnt++)

{

if((a[c][cnt] != 0) && (visited[cnt] == 0))

{

if(a[c][cnt] < min)

{

min = a[cnt][0] + a[c][cnt];

}

temp = a[c][cnt];

near_city = cnt;

}

}

if(min!= 999)

{

cost = cost + temp;

}

return near_city;

}

void min_cost(int city)

{

int near_city;

visited[city] = 1;

printf(“%d “, city + 1);

near_city = tsp(city);

if(near_city == 999)

{

near_city = 0;

printf(“%d”, near_city + 1);

cost = cost + a[city][near_city];

return;

}

min_cost(near_city);

}

void get()

{

int i, j;

printf(“Enter Total Number of Cities:\t”);

scanf(“%d”, &n);

printf(“\nEnter Cost Matrix\n”);

for(i = 0; i < n; i++)

{

printf(“\nEnter %d Elements in Row[%d]\n”,n, i + 1);

for(j = 0; j < n; j++)

{

scanf(“%d”, &a[i][j]);

}

visited[i] = 0;

}

printf(“\nEntered Cost Matrix\n”);

for(i = 0; i < n; i++)

{

printf(“\n”);

for(j = 0; j < n; j++)

{

printf(“%d “, a[i][j]);

}

}

}

/*

================================== OUTPUT ======================================

int main()

{

get();

printf(“\n\n the path is:\n\n”);

min_cost(0);

printf(“\n\nMinimum Cost: \t”);

printf(“%d\n”, cost);

return 0;

}

student@sdl17:~$ gcc tsp.c

student@sdl17:~$ ./a.out

Enter Total Number of Cities: 5

Enter Cost Matrix

Enter 5 Elements in Row[1]

1 2 2 5 3

Enter 5 Elements in Row[2]

1 2 4 5 6

Enter 5 Elements in Row[3]

1 2 4 5 6

Enter 5 Elements in Row[4]

1 2 5 4 8

Enter 5 Elements in Row[5]

7 4 3 2 5

Entered Cost Matrix

1 2 2 5 3

1 2 4 5 6

1 2 4 5 6

1 2 5 4 8

7 4 3 2 5

the path is:

1 5 4 3 2 1

Minimum Cost: 13

student@sdl17:~$

*/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s