Skip to content

Instantly share code, notes, and snippets.

@kuoe0 kuoe0/GT-TSP-DP.cpp
Last active Jun 26, 2018

Embed
What would you like to do?
[Algorithm] Traveling Salesman's Problem - DP solution - http://kuoe0.ch/1878/algorithm-traveling-salesman-s-problem-dp-solution
/*=============================================================================
# FileName: GT-TSP-DP.cpp
# Desc: Traveling Salesman Problem - DP solution
# Author: KuoE0
# Email: kuoe0.tw@gmail.com
# HomePage: http://kuoe0.ch/
# Version: 0.0.1
# LastChange: 2012-10-11 20:59:01
# History:
=============================================================================*/
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, src;
vector< vector< int > > graph, dp;
// initial status
void init() {
for ( int i = 0; i < n; ++i )
dp[ 1 << i ][ i ] = graph[ src ][ i ];
}
// TSP recursive
int TSP( int status, int x ) {
if ( dp[ status ][ x ] != -1 )
return dp[ status ][ x ];
int mask = 1 << x;
dp[ status ][ x ] = 1e9;
for ( int i = 0; i < n; ++i )
if ( i != x && ( status & ( 1 << i ) ) )
dp[ status ][ x ] = min( dp[ status ][ x ], TSP( status - mask, i ) + graph[ i ][ x ] );
return dp[ status ][ x ];
}
int main() {
scanf( "%d %d", &n, &src );
graph = vector< vector< int > >( n, vector< int >( n ) );
dp = vector< vector< int > >( 1 << n, vector< int >( n, -1 ) );
for ( int i = 0; i < n; ++i )
for ( int j = 0; j < n; ++j ) {
int x;
scanf( "%d", &x );
graph[ i ][ j ] = x;
}
init();
printf( "%d\n", TSP( ( 1 << n ) - 1, src ) );
return 0;
}
@RajeshUppala

This comment has been minimized.

Copy link

commented Jan 29, 2015

Your TSP implementation is awesome. Can you make changes to your code and print the path
Thanks in advance!!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.