# C Program to Implement Branch and Bound Method

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.

1. `/*Branch and Bound Algorithm for Travelling Sales Person*/`
2. `#include<stdio.h>`
3. `#include<conio.h>`
4. `int a[10][10], visited[10], n, cost = 0;`
5. `void get() {`
6. `    int i, j;`
7. `    printf("Enter No. of Cities: ");`
8. `    scanf("%d", &n);`
9. `    printf("\nEnter Cost Matrix: \n");`
10. `    for (i = 0; i < n; i++) {`
11. `        printf("\n Enter Elements of Row# : %d\n", i + 1);`
12. `        for (j = 0; j < n; j++)`
13. `            scanf("%d", &a[i][j]);`
14. `        visited[i] = 0;`
15. `    }`
16. `    printf("\n\nThe cost list is:\n\n");`
17. `    for (i = 0; i < n; i++) {`
18. `        printf("\n\n");`
19. `        for (j = 0; j < n; j++)`
20. `            printf("\t % d", a[i][j]);`
21. `    }`
22. `}`
23. `void mincost(int city) {`
24. `    int i, ncity;`
25. `    visited[city] = 1;`
26. `    printf("%d –>", city + 1);`
27. `    ncity = least(city);`
28. `    if (ncity == 999) {`
29. `        ncity = 0;`
30. `        printf("%d", ncity + 1);`
31. `        cost += a[city][ncity];`
32. `        return;`
33. `    }`
34. `    mincost(ncity);`
35. `}`
36. `int least(int c) {`
37. `    int i, nc = 999;`
38. `    int min = 999, kmin;`
39. `    for (i = 0; i < n; i++) {`
40. `        if ((a[c][i] != 0) && (visited[i] == 0))`
41. `            if (a[c][i] < min) {`
42. `                min = a[i][0] + a[c][i];`
43. `                kmin = a[c][i];`
44. `                nc = i;`
45. `            }`
46. `    }`
47. `    if (min != 999)`
48. `        cost += kmin;`
49. `    return nc;`
50. `}`
51. `void put() {`
52. `    printf("\n\nMinimum cost:");`
53. `    printf("%d", cost);`
54. `}`
55. `void main() {`
56. `    get();`
57. `    printf("\n\nThe Path is:\n\n");`
58. `    mincost(0);`
59. `    put();`
60. `}`

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.