C program for Travelling Salesman Problem using Branch and Bound

Mr Coder August 23, 2012 7




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 matrix 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 C program for Travelling salesman problem using branch and bound technique. If you have any issues with the program, let us know in form of comments.

7 Comments »

  1. pandoracharms October 14, 2012 at 12:20 pm - Reply

    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. sadprogrammer November 24, 2012 at 4:49 pm - Reply

    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
    suppose adjacency matrix is
    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,
    this progaram gives the answer
    1-4-3-2-1 and cost give is 75, i know its ages since u posted this, but plz rectify it!

  3. thao March 16, 2013 at 6:48 am - Reply

    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. thao March 16, 2013 at 11:49 pm - Reply

    I hope to hear from you soon since this is pretty urgent

  5. okbariyo June 17, 2013 at 7:05 pm - Reply

    this algo was wrong

  6. antoshkaplus July 6, 2013 at 12:55 pm - Reply

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

Leave A Response »