salseman.java

一个简单的货郎担问题

public class SalseMan {
	int node,cost;
	
	public static void main(String[] args) {
		SalseMan sm = new SalseMan();
		final int n = 4;
		int[][] m = { { 0, 10, 20, 30 }, { 5, 0, 9, 10 }, { 6, 13, 0, 12 },
				{ 8, 8, 9, 0 } };
		BestWay bw = new BestWay(m, n);
		BestNode bn = new BestNode(m, n);
		boolean[] b = new boolean[n];
		for (int i = 0; i < n; i++) {
			b[i] = false;
		}
		b[0] = true;
		int min = 1000;
		for (int i = 1; i<n; i++) {
			b[i] = true;
			sm.cost = m[0][i] + bw.bestWay(i,b);
			if (min > sm.cost) {
				min = sm.cost;
				sm.node = i;
			}
			b[i] = false;
		}
		System.out.println("最短路径的长度为：" + min);

		int[] p = new int[10];
		int k = 0;
		p[k] = sm.node;
		k++;
		int next;
		b[sm.node] = true;
		next = bn.bestNode(sm.node, b);
		while(sm.node != next) {
			p[k] = next;
			k++;
			sm.node = next;
			b[sm.node] = true;
			next = bn.bestNode(sm.node, b);
		}
		p[k] = '\0';
		System.out.print("最短路径的路线为："+1);
		for(k=0;p[k]!='\0';k++) {
			System.out.print(p[k]+1);			
		}
		System.out.print(1);
	}

}