巡回セールスマン問題 - Programming @ wiki

巡回セールスマン問題を解くとき、はじめに隣接行列を定義しておく。
また、自分から自分へのコストは、後を楽にするためにINT-MAXとしておく。

こんな感じ。
& 2 6 4
2 & 4 6
6 4 & 2
4 6 2 &

& = INT-MAX

動的計画法により解くので、コストを入れておく行列cost[cityNum-1][cityNum-1]も作っておく。

開始点のノードは0とする。

以下ソース

void TSP (int size) {
	
	int i,j,step,ansVal,minVal;
	
	for(i=0;i<size-1;i++) cost[i][0] = adj[i+1][0];
	for(step=1;step<size-1;++step) {
		
		for(i=0;i<size-1;++i) {
			minVal = INT_MAX;
			for(j=0;j<size-1;++j) {
				if(i != j) minVal = min(minVal, (cost[j][step-1] + adj[i+1][j+1]) );
			}
			cost[i][step] = minVal;
		}
	}
	
	ansVal = INT_MAX;
    	for (i=0;i<size-1;++i) ansVal = min(ansVal, cost[i][size-2]);
   	return;
}