How do I keep track of path in TSP?

1k views Asked by At

I found a simple solution to a TSP problem using bitmask here.

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;
}

What if I want to know the path of the solution. How do I implement that? What's come in my mind is to add a variable track[status][list of path]. But, I don't think it's a good solution. What is the best way to keep track of the path?

0

There are 0 answers