Branch and Bound Algorithm in C

This is a C Program to solve TSP. The Traveling Salesman Problem states that, given a list of cities and the distances between each pair of cities, calculate the shortest distance route that visits each city exactly once and route returns to original city. It is an NP-hard problem.

Here is source code of the C Program to Implement Branch and Bound Method to Perform a Combinatorial Search. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*Branch and Bound Algorithm for Travelling Sales Person*/

```
#include<stdio.h>
```
```
#include<conio.h>
```

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

```
void get() {
```
```
    int i, j;
```
```
    printf("Enter No. 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 list is:\n\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);
```
```
}
```
```
void main() {
```
```
    get();
```
```
    printf("\n\nThe Path is:\n\n");
```
```
    mincost(0);
```
```
    put();
```
```
}
```

Output:

$ gcc TSPBranchBound.c
$ ./a.out
 
Enter No. of Cities: 6
Enter Cost Matrix: 
99 10 15 20 99 8
5 99 9 10 8 99
6 13 99 12 99 5
8 8 9 99 6 99
99 10 99 6 99 99
10 99 5 99 99 99
 
Enter Elements of Row# : 1
Enter Elements of Row# : 2
Enter Elements of Row# : 3
Enter Elements of Row# : 4
Enter Elements of Row# : 5
Enter Elements of Row# : 6
 
The Path is:
 
1 –>6 –>3 –>4 –>5 –>2 –>1
 
Minimum cost:46

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Check Whether a Given Graph is Bipartite or not

» Next - C Program to Solve Stable Marriage Problem

Related Posts:

Recommended Articles: