30天挑战数据结构和算法之第9、10天最短路径

October 26 2019

终于找到工作了，面试的过程说起来很惭愧，一共就一道算法题，给了我一个半小时，我还没做出来。

题目很简单，就是让我求一个最短路径的算法。由于我之前从来没接触过最短路径的问题，当接到这个题目的时候，我内心是崩溃的。好在面试是机考，并且允许我上网找方案，这是我以前从来没遇到过的。

好不容易找到一篇送快递的最短路径的文章，和题目有某种千丝万缕的关系。其中有一句话特别能让我产生共鸣，

首先应该想到的是最笨最常见的做法，那就是枚举法，列出所有的路径，求出所有距离的最小值。而不应该去企图从Dijkstra或者是其他的图算法那里找突破口，说明你对图算法还了解的不深。

我确实应该从最简单的枚举法开始入门。一个半小时根本不够我去学一种高级的算法，并理解它，于是我去试着理解门槛比较低的枚举法。很可惜的是，因为代码本身有点问题，加上紧张的情绪，我花了大部分的时间在试着将代码运行起来。没有能在一个半小时内去理解枚举法的核心思想。

本来以为没有机会的我，却意外地收到了公司的offer，愿意再给我一次机会。对于这样的结果，其实我自己是挺羞愧的。我这人没什么优点，除了特别轴，我不相信我理解不了枚举法。所以，这两天我一直在研究最短路径的枚举解法。

代码实现

下面是在原Java版本的枚举法的基础上，修复了BUG后的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class MyPoint {
		int x, y;

		public MyPoint(int i, int j) {
				x = i;
				y = j;
		}

		public static void main(String[] args) {
				start = new MyPoint(0, 0);
				points = new MyPoint[] {
						new MyPoint(1, 1),
						new MyPoint(2, 3),
						new MyPoint(3, 2),
						new MyPoint(4, 3)
				};
				int minVal = minPath();
				System.out.println("-----------最短路径----------");
				System.out.println(minVal);
		}

		private static int min = Integer.MAX_VALUE;
		private static MyPoint start;
		private static MyPoint[] points; 

		private static int minPath() {
				boolean[] b = new boolean[points.length];
				int path = 0;
				for(int i = 0; i < points.length; i++) {
						System.out.println("--------路线" + i + "---------");
						path = getDis(start, points[i]);
						dfs(i, path, b, 1, points.length);
				}
				return min;
		}

		private static void dfs(int index, int path, boolean[] b, int level, int length)
		{
				if(level == length) {
						// 起点到最后一个点的距离
						path += getDis(start, points[index]);
						System.out.println("path = " + path);
						// 计算出最短路径
						if(path < min) min = path;
						return;
				}
				b[index] = true;
				for(int i = 0; i < points.length; i++) {
						if(!b[i]) {
								// 初始路径的备份
								int pathcopy = path;
								path += getDis(points[index], points[i]);
								dfs(i, path, b, level+1, length);
								path = pathcopy;
						}
				}
				b[index] = false;
		}

		private static int getDis(MyPoint start, MyPoint point) {
				int distance = Math.abs(start.x-point.x) + Math.abs(start.y-point.y);
				System.out.println("start(" + start.x + "," + start.y + ") -> point(" + point.x + "," + point.y + ")  = " + distance);
				return distance;
		}
}

其中minPath方法就是最短路径枚举法的封装。这个函数有个for循环，遍历的内容是从起点到随机送货点的数组中的每一个点。通过getDis函数获取了起点到某个点的距离后，调用dfs递归方法求从该点回到起点的每一种可能的走法。

dfs函数是枚举法的核心所在，它接受5个参数，其中index为当前所在点，path用来累加路径，b数组是一个布尔类型的数组（数组长度和随机送货点数组长度相同且一一对应，true表示当前送货点已经走过），level是当前的递归的深度，length是递归的总深度。因为dfs函数的递归调用包裹在一层for循环中，内容是所有随机送货点，且通过b数组来判断当前送货点是否已经走过，所以我们可以完成从某个点开始到剩余其它送货点的所有可能走法以及最短路径。最后当递归深度和总递归深度一致的时候，说明某条线路走到了最后一个送货点，然后求起点到最后一个送货店的距离就可以完成一次完整的送货路线，求出此路线的路径长度。通过不断比对每条路线的长度，求出最后的最短路径。

我个人觉得b数组是dfs函数的灵魂，就是因为b数组的条件限制，才能够完成点到点的各种选择。

时间复杂度

时间复杂度我是这样计算的，不知道对不对

对于minPath中有一个for循环，遍历的长度为数组长度n。dfs函数中for循环中调用递归，其中每一个元素除了自身都会遍历其它元素，所以我觉得复杂度为(n-1)^2。综上，总的时间复杂度为O(n*((n-1)^2))

最后来说一下，这个Java实现的枚举法还有点瑕疵。就是没法输出所有的路线，有些头部路线缺省了。可以肯定的是，随着送货点越来越多，肯定是不推荐这种解法的，毕竟枚举法的核心思想是暴力循环破解。这是一种相当费时的操作。这个时候可能就要研究更高级的最短路径算法了。

avatar

chilihotpot

You Are The JavaScript In My HTML