算法学习：关于最短路径的计算(深度优先搜索)
第一次写文章，写得不够好的地方还望大家多多谅解，感谢指正
今天做了一条题目，只有一张地图(如图在这里插入图片描述),输入任意起点和终点,求从起点到终点的最小代价。
另外，从一个点(i)到另一个点(j)的代价计算方法为：All=Weight[i]+maps[i][j]+Weight[j],其中Weight[i]表示点i的权值，maps[i][j]表示点i到点j的代价，Weight[j]表示点j的权值。
这道题其实比较简单，采用的算法的主要思想就是深度优先搜索。我的做法就是首先给每个点标上序号，主要是为了方便程序设计，如图所示，然后建立一个二维数组maps[][],表示点i到点j之间的代价，再创立一个String数组。用来存放每个点的名字，主要用于输出，创立一个boolean类型的数组flag[]，表示第i个点是否有被访问过，创立一个int类型的数组weight[]，表示每个点的权值。
这道题的主要解决思想就是在这个图中，先创立一个int型变量Min=10000，记录从起点到终点的最小代价，创立两个数组Array[]和MinArray[]，分别记录访问过的点和代价最小路径所经过的点。
从一个点(假设为A)出发，flag[A]=true,访问一个临近的点(假设为B)，把B设置为已访问(flag[B]=true)，All=All+Weight[A]+maps[A][B]+Weight[B]，把B存进Array[]中；然后再访问B的一个临近点(假设为C)，把C设置为以访问(flag[C]=true)，All=All+Weight[B]+maps[B][C]+Weight[C]，把C存进Array[]中，一直这样访问下去，直到访问到某个点(假设为F)，flag[F]=true，All=All+Weight[上一个点]+maps[上一个点][C]+Weight[C]，把F存进Array[]中，判断这个点F是不是我们要访问的终点。
如果是的话，将从A点到F点的代价与Min比较，如过小于Min，则把从A到F的所经过的点存进MinArray[]中，然后返回上一层(这里要注意：返回上一层的时候记得要把访问完的点flag设置为false，表示该点未被访问，一定要注意，否则从其它路径出发的话是没法访问到这个点的，一定要切记)，访问F的上一个点(假设为E)，再从E开始访问与E相邻的除了F以外的所有点，寻找其它可以到达F的路径，直到与E的相邻所有路径都被访问过后，再返回E的上一层(假设为D)，再从D开始访问与D相邻的除了E以外的所有点，寻找其它可以到达F的路径，一直类推，直到把从起点到终点的所有路径都走过一遍。
如果不是的话，并且点F已经没有与其相邻的点，则直接返回上一层，flag[F]=false,再按照上面的思路继续下去。
不难看出这里用到的思想其实就是一种回溯的想法。再次提醒，每返回上一层的时候都要把本次访问的点的flag设置为false，否则下次无法访问。
下面贴上代码，可能写得有点乱，结合解题思路慢慢看应该不难懂：
import java.util.Scanner;
public class Homework {
/**
* @param args
*/
public static int maps[][]={{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //该数组用来表示每个点之间的距离值，0表示两个点之间无法直接到达，第一行和第一列不使用，方便下面的处理
{0,0,71,0,0,0,0,0,151,0,0,0,0,0,0,0,0,0,0,0,0}, //1,表示点Oradea
{0,71,0,75,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //2,表示点Zerind
{0,0,75,0,118,0,0,0,140,0,0,0,0,0,0,0,0,0,0,0,0,0}, //3,表示点Arad
{0,0,0,118,0,111,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //4,表示点Timisoara
{0,0,0,0,111,0,70,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //5,表示点Lugoj
{0,0,0,0,0,70,0,75,0,0,0,0,0,0,0,0,0,0,0,0,0}, //6,表示点Mehadia
{0,0,0,0,0,0,75,0,0,0,120,0,0,0,0,0,0,0,0,0,0}, //7,表示点Drobeta
{0,151,0,140,0,0,0,0,0,80,0,99,0,0,0,0,0,0,0,0,0}, //8,表示点Sibiu
{0,0,0,0,0,0,0,0,80,0,146,0,97,0,0,0,0,0,0,0,0}, //9,表示点Rimnicu Vilcea
{0,0,0,0,0,0,0,120,0,146,0,0,138,0,0,0,0,0,0,0,0}, //10,表示点Craiova
{0,0,0,0,0,0,0,0,99,0,0,0,0,0,0,0,0,211,0,0,0}, //11,表示点Fagaras
{0,0,0,0,0,0,0,0,0,97,138,0,0,0,0,0,0,101,0,0,0}, //12,表示点Pitesti
{0,0,0,0,0,0,0,0,0,0,0,0,0,87,0,0,0,0,0,0,0}, //13,表示点Neamt
{0,0,0,0,0,0,0,0,0,0,0,0,0,87,0,92,0,0,0,0,0}, //14,表示点Iasi
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,92,0,142,0,0,0,0}, //15,表示点Vaslui
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,142,0,85,0,98,0}, //16,表示点Urziceni
{0,0,0,0,0,0,0,0,0,0,0,211,101,0,0,0,85,0,90,0,0}, //17,表示点Bucharest
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,90,0,0,0,0}, //18,表示点Giurgiu
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,98,0,0,0,86}, //19,表示点Hirsova
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,86,0}, //20,表示点Eforie
};
public static String name[]= {" ","Oradea","Zerind","Arad","Timisoara","Lugoj","Mehadia","Drobeta","Sibiu","Rimnicu Vilcea"
,"Craiova","Fagaras","Pitesti","Neamt","Iasi","Vaslui","Urziceni","Bucharest","Giurgiu","Hirsova","Eforie"};
public static boolean flag[]= {false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false};//表示每个点是否被遍历过
public static int weight[]= {0,380,374,366,329,244,241,242,253,193,160,176,100,234,226,199,80,0,77,151,161};//每个点的权值
public static int []array=new int[21]; //array存放以访问过的点
public static int MinArray[]=new int[21]; //存放最小代价所经过的点
public static int index=1; //下标，用来指示array中最后一个被访问的点的下一个位置，即假设最后一个 点为F，则index指向F的下一个位置
public static int Min=100000; //最小代价，初始为10000
public static int StartPoint; //起点
public static int EndPoint; //终点
public static void main(String[] args) {
System.out.println("请输入开始点和结束点(直接输入点的代号即可)：");
Scanner reader=new Scanner(System.in);
StartPoint=reader.nextInt();
EndPoint=reader.nextInt();
solution(StartPoint,0,0);
System.out.println("最小值为："+Min);
System.out.print("所经过的点为："+"{");
for(int j=1;MinArray[j]!=EndPoint;j++) { //输出代价最小的路径
System.out.print(name[MinArray[j]]+",");
}
System.out.print(name[EndPoint]+"}");
}
public static void solution(int start,int lastStart,int all) { //start表示当前访问的点，lastStart表示上一个点，all表示当前代价总和
array[index++]=start; //每访问一个新的点，都把它存进array中
if(start==EndPoint) { //如果这次访问的点等于目的点，则比较与上一个局部最优解的代价大小
if(all<Min) {
Min=all;
for(int j=1;j<21;j++) {
MinArray[j]=array[j]; //把当前最优解存进MinArray[]中
}
}
return;
}
int i;
for(i=1;i<=EndPoint;i++) {
if((maps[start][i]!=0)&&(flag[i]==false)) { //如果从这次访问的点到下一个点的距离不等于零并且下一个点未被访问过
if(start==StartPoint) { //如果该点为起点，即重新找另外一条路径
array[1]=start;
index=2;
for(int j=2;j<=20;j++) { //把array中的记录清零
array[j]=0;
}
all=weight[StartPoint];
}
flag[i]=true; //访问下一个点i，flag[i]==true
solution(i,start,all+maps[start][i]+weight[i]);
flag[i]=false; //访问点i完成，flag[i]==false
index--;
array[index]=0; //把点i退出来，该位置重新置零
}
}
}
}
这篇博客写到这里就基本完成了，第一次写博客，难免会有另大家不满意的地方，欢迎大家指出来改正，谢谢。