Printing Traveled Path in Traveling Salesman Problem

Revision en3, by 1507002, 2020-06-12 22:09:18

Could anyone please tell me how to get the traveled path for Traveling Salesman Problem?

My code is here:

int TSP(int i, int mask){
	if(mask == (1<<n)-1) return w[i][0];
	if(mem[i][mask] != -1) return mem[i][mask];

	int ans = INF;
	for(int j=0; j<n; j++){
		if(w[i][j] == INF) continue;
		if( (mask & (1<<j)) == 0){
			int result = TSP(j, (mask | (1<<j)) ) + w[i][j];
			ans = min(ans, result);
		}
	}
	return mem[i][mask] = ans;
}
Tags #dynamic_programmign, #tsp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English 1507002 2020-06-12 22:09:18 20
en2 English 1507002 2020-06-12 20:22:22 6 Tiny change: 'oblem?**\n****\nMy code ' -> 'oblem?**\n\n\nMy code '
en1 English 1507002 2020-06-12 20:21:40 527 Initial revision (published)