寻找最短路径

题目：给定一个起点和一个终点。在一个8*8的棋盘上找出一条最短的路径。

 

 

import java.util.ArrayList;
//主要是采用广度优先的算法。
/**
 *             广度度优先搜索

宽度优先搜索并不是一种很优秀的算法，只里只是简单介绍一下它。

具体方法是：

1、  从A点开始依次展开得到AB、AC、AD、AE四个新结点（第二层结点），当然每个新结点要记录下其距离；

2、  再次以AB展开得到ABC、ABD、ABE三个新结点（第三层结点），而由AC结点可展开得到ACB、ACD、ACE三个新结点，自然AD可以展开得到ADB、ADC、ADE，AE可以展开得到AEB、AEC、AED等新结点，对于每个结点也须记录下其距离；

3、  再把第三层结点全部展开，得到所有的第四层结点：ABCD、ABCE、ABDC、ABDE、ABEC、ABED……AEDB、AEDC，每个结点也需记录下其距离；

4、  再把第四层结点全部展开，得到所有的第五层结点：ABCDE、ABCED、…、AEDBC、AEDCB，每个结点也需记录下其距离；

5、  到此，所有可能的结点均已展开，而第五层结点中最小的那个就是题目的解了。
 */
public class T6 {
	//模拟一个棋盘
	String num[][] = new String[8][8];
	//用来模拟队列的容器
	ArrayList<point> duilie = new ArrayList<point>();

	public static void main(String[] args) {
		T6 test = new T6();
	}

	T6() {
		//对数组初始化，""代表没有访问过
		for (int i = 0; i < num.length; i++) {
			for (int j = 0; j < num[0].length; j++) {
				num[i][j] = "";
			}
		}
		//寻找最短路径,假如起点是7，0 寻找到0，7这个点的最短路径
		zuiduan(7, 0);
		
		System.out.println("最短路径是："+num[0][7].toString()+"0,7结束");
	
	}

	public void xunzhao(int x, int y ,String lujing) {
		if (!(x < 0 || x > 7 || y < 0 || y > 7) && num[x][y].equals("")) {

			// 设置为访问过。并记录步数
			num[x][y]=lujing;
			point id = new point();
			id.setX(x);
			id.setY(y);
			// 入队
			duilie.add(id);
		}
	}

	public void zuiduan(int i, int j) {
		// 访问原点，设置为访问过。
		
		point id = new point();
		
		num[i][j] ="开始";
		id.setX(i);
		id.setY(j);
		// 入队
		duilie.add(id);
		// 循环队列
		while (duilie.size() != 0) {
			//终止循环的条件
			if (!num[0][7].equals(""))
				break;
			// 出队
			point id1 = duilie.get(0);
			duilie.remove(0);
			// 循环，一次搜索隔壁点
			int x = id1.getX();
			int y = id1.getY();
			String lujing=num[x][y]+x+","+y+"-> ";
			// 判断，如果没有出界并且没有访问过
			xunzhao(x - 1, y,lujing);
			xunzhao(x + 1, y,lujing);
			xunzhao(x, y - 1,lujing);
			xunzhao(x, y + 1,lujing);
		}

	}
//用来记录寻找的每一个点
	class point {
		int x;
		int y;
		public int getX() {
			return x;
		}

		public void setX(int x) {
			this.x = x;
		}

		public int getY() {
			return y;
		}

		public void setY(int y) {
			this.y = y;
		}
	}
}

 寻找最短路径,假如起点是7，0 寻找到0，7这个点的最短路径

输出结果如下：

最短路径是：

开始7,0-> 6,0-> 5,0-> 4,0-> 3,0-> 2,0-> 1,0-> 0,0-> 0,1-> 0,2-> 0,3-> 0,4-> 0,5-> 0,6-> 0,7结束