C program for Travelling Salesman Problem using Branch and Bound

# C program for Travelling Salesman Problem using Branch and Bound

23247
14
SHARE

C program for travelling salesman problem using branch and bound : Branch and bound (BB or B&B) is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. A branch-and-bound algorithm consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded, by using upper and lower estimated bounds of the quantity being optimized.

Previously we have seen C program for travelling salesman problem using operational search, today we will learn how to write a C code using combinatorial optimization i.e. Branch and Bound Algorithm.

Travelling Salesman Problem can be modeled as an undirected weighted graph, such that cities are the graph’s vertices, paths are the graph’s edges, and a path’s distance is the edge’s length. It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once. Often, the model is a complete graph (i.e. each pair of vertices is connected by an edge). If no path exists between two cities, adding an arbitrarily long edge will complete the graph without affecting the optimal tour.

I have written a C code of the above logic of Travelling Salesman Problem using branch and bound technique which accepts number of cities as user input and then prompts user to enter the cost and then it calculates the optimal path for the TSP and displays the optimal path as output.

C program of Travelling Salesman Problem using Branch and Bound :

```#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int a[10][10],visited[10],n,cost=0;
void get()
{
int i,j;
printf("----------------------------------------------------------------------\n");
printf("-------------------made by C code champ ------------------------------\n");
printf("----------------------------------------------------------------------\n");
printf("\n\n\t TRAVELLING SALESMAN PROBLEM SOLUTION IN C\n");
printf("\n\nEnter Number of Cities: ");
scanf("%d",&n);

printf("\nEnter Cost Matrix: \n");
for( i=0;i<n;i++)
{
printf("\n Enter Elements of Row # : %d\n",i+1);
for( j=0;j<n;j++)
scanf("%d",&a[i][j]);
visited[i]=0;
}

printf("\n\nThe Cost Matrix is:\n");

for( i=0;i<n;i++)
{
printf("\n\n");
for( j=0;j<n;j++)
printf("\t%d",a[i][j]);

}

}

void mincost(int city)
{
int i,ncity;
visited[city]=1;
printf("%d ===> ",city+1);
ncity=least(city);

if(ncity==999)
{
ncity=0;
printf("%d",ncity+1);
cost+=a[city][ncity];
return;
}

mincost(ncity);
}

int least(int c)
{
int i,nc=999;
int min=999,kmin;
for(i=0;i<n;i++)
{
if((a[c][i]!=0)&&(visited[i]==0))
if(a[c][i]<min)
{
min=a[i][0]+a[c][i];
kmin=a[c][i];
nc=i;
}
}

if(min!=999)
cost+=kmin;
return nc;
}

void put()
{
printf("\n\nMinimum cost:");
printf("%d",cost);
}

int main()
{
get();
printf("\n\nThe Path is:\n\n");
mincost(0);
put();
getch();
}```

We hope you all enjoyed the technique. If you have any issues with the program, let us know in form of comments.

1. Attractive section of content. I just stumbled upon your weblog and in accession capital to assert that I get in fact enjoyed account your blog posts. Anyway I will be subscribing to your feeds and even I achievement you access consistently rapidly.

2. well i liked the algo(I found this out cuz the one they taught at college was too difficult) unfortunately though this algo has a bug
0 10 12 15
10 0 20 26
12 20 0 30
15 26 30 0
optimal path is 1-3-2-4-1 and cost is 73,
1-4-3-2-1 and cost give is 75, i know its ages since u posted this, but plz rectify it!

your comment is very interesting, however I found that you’re interpreting the adjacency matrix in a bad way. Indeed if you put the following adj matrix:

1000.00 10.00 12.00 15.00

10.00 1000.00 20.00 26.00

12.00 20.00 1000.00 30.00

15.00 26.00 30.00 1000.00

you can easily check that the code works fine. As an example the output of this code is:

The Path is:

1 ===> 4 ===> 3 ===> 2 ===> 1

Minimum cost:75

Then, if we consider your example it works as expected.

3. Hello Mr.Coder, I’ve been trying to look for a solution for the Travelling salesman problem which is gonna due soon. This code of yours is nice, but could you please explain how the algorithm works? An as the comment above said, it does have some bug. If somehow you could go over the code again to check it again, that would be SO MUCH appreciated. I’ve tried to catch where you might have gone wrong but since i’m not quite sure how the algorithm works, it’s quite impossible. Thank you for your time!

4. this is not branch and bound technique. the guy coded greedy algorithm, which takes minimum unused edge for each vertex iteratively.

5. This program doesn’t work for all cases, and thus leads to wrong answers.
So beware, this guy has just coded some random codes. This is not the actual solution.