Implement Travelling Sales Person problem using Branch and Bound approach.

 #include <stdio.h>

#include <stdlib.h>

#include <limits.h>

#define N 4  // Number of cities

int finalPath[N + 1];

int visited[N];

int finalRes = INT_MAX;

// Copy current path to final path

void copyToFinal(int currPath[]) {

    for (int i = 0; i < N; i++)

        finalPath[i] = currPath[i];

    finalPath[N] = currPath[0];

}

// Find minimum edge cost from city i

int firstMin(int graph[N][N], int i) {

    int min = INT_MAX;

    for (int k = 0; k < N; k++)

        if (graph[i][k] < min && i != k)

            min = graph[i][k];

    return min;

}

// Find second minimum edge cost from city i

int secondMin(int graph[N][N], int i) {

    int first = INT_MAX, second = INT_MAX;

    for (int j = 0; j < N; j++) {

        if (i == j)

            continue;

        if (graph[i][j] <= first) {

            second = first;

            first = graph[i][j];

        } else if (graph[i][j] <= second && graph[i][j] != first)

            second = graph[i][j];

    }

    return second;

}

// TSP Recursive function using Branch and Bound

void TSPRec(int graph[N][N], int currBound, int currWeight, int level, int currPath[]) {

    if (level == N) {

        if (graph[currPath[level - 1]][currPath[0]] != 0) {

            int currRes = currWeight + graph[currPath[level - 1]][currPath[0]];

            if (currRes < finalRes) {

                copyToFinal(currPath);

                finalRes = currRes;

            }

        }

        return;

    }

    for (int i = 0; i < N; i++) {

        if (graph[currPath[level - 1]][i] != 0 && visited[i] == 0) {

            int temp = currBound;

            currWeight += graph[currPath[level - 1]][i];

            if (level == 1)

                currBound -= ((firstMin(graph, currPath[level - 1]) + firstMin(graph, i)) / 2);

            else

                currBound -= ((secondMin(graph, currPath[level - 1]) + firstMin(graph, i)) / 2);

            if (currBound + currWeight < finalRes) {

                currPath[level] = i;

                visited[i] = 1;

                TSPRec(graph, currBound, currWeight, level + 1, currPath);

            }

            currWeight -= graph[currPath[level - 1]][i];

            currBound = temp;

            for (int j = 0; j < N; j++)

                visited[j] = 0;

            for (int j = 0; j <= level - 1; j++)

                visited[currPath[j]] = 1;

        }

    }

}

// Function to solve TSP

void TSP(int graph[N][N]) {

    int currPath[N + 1];

    int currBound = 0;

    for (int i = 0; i < N; i++) {

        currBound += (firstMin(graph, i) + secondMin(graph, i));

    }

    currBound = (currBound & 1) ? currBound / 2 + 1 : currBound / 2;

    visited[0] = 1;

    currPath[0] = 0;

    TSPRec(graph, currBound, 0, 1, currPath);

}

// Main function

int main() {

    int graph[N][N] = {

        {0, 10, 15, 20},

        {10, 0, 35, 25},

        {15, 35, 0, 30},

        {20, 25, 30, 0}

    };

    TSP(graph);

    printf("Minimum cost: %d\n", finalRes);

    printf("Path Taken: ");

    for (int i = 0; i <= N; i++)

        printf("%d ", finalPath[i]);

    printf("\n");

    return 0;

}

Output: