寻找最短路径

题目：给定一个起点和一个终点。在一个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结束