Travelling Salesman Problem (TSP) Algorithm Source Code (C/C++)



// @BEGIN_OF_SOURCE_CODE

#include <cstdio>
#include <cstring>
using namespace std;

bool vis [CITY] [1 << CITY]; // is_visited
int val [CITY] [1 << CITY]; // cost at particular state
int weight [CITY] [CITY]; // given weight

int dp (int at, int mask)
{
    if ( mask ==  (1 << CITY) - 1 ) { // all visited
        vis [at] [mask] = true;
        return val [at] [mask];
    }

    if ( vis [at] [mask] ) return val [at] [mask];
    vis [at] [mask] = true;

    int ans = inf;
    int cost;

    for ( int i = 0; i < CITY; i++ ) {
        if ( weight [at] [i] != -1 && (mask & (1 << i)) == 0 ) {
            cost = dp (i, mask | (1 << i)) + weight [at] [i];
            if ( ans > cost ) ans = cost;
        }
    }

    return val [at] [mask] = ans;
}

int main ()
{
    memset (vis, false, sizeof (vis));
    memset (weight, -1, sizeof (weight));
    printf ("Cost : %d\n", dp (0, 1));

    return 0;
}

// @END_OF_SOURCE_CODE

Advertisements

4 thoughts on “Travelling Salesman Problem (TSP) Algorithm Source Code (C/C++)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s