3.6 最短路径

3.6.1 问题描述

最短路径问题(Shortest path problem)：再不回退的前提下，找到A到F的最短路径

3.6.2 算法思路

A到B1的最短路径为4，前序节点为A；
A到B2的最短路径为5，前序节点为A;
A到C1的最短路径，我们可以看出，只有B1可以到达C1，所以最短路径为4+2=6，前序节点为B1；
A到C2的最短路径，我们可以看出，B1和B2都可以到达C2，其中经过B1的最短路径为4+3=7，经过B2的最短路径为5+8=13，所以A到C2的最短路径为7，前序节点为B1。
依次类推，得出下面的信息。

动态规划的思想：

  • 问题分阶段：我们把求A到F最短路径这个大问题，分为了一个个小问题
  • 阶段有依赖：每一个节点到A的距离，都依赖于它的前序节点到A的距离
  • 依赖有重叠：因为记录了每个节点的前序节点和最短路径，这样就可以不用再重复计算前序节点之前的路径。

3.6.3 代码实现

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
public static LinkedList<String> getByDP(HashMap<String, LinkedList<String>> routes, HashMap<String, LinkedList<Integer>> distances,	String origin, String destination){
	HashMap<String, Integer> short_distance = new HashMap<String, Integer>();//存该点到起点的最短距离
	HashMap<String, String> short_routes = new HashMap<String, String>();//到起点的最点距离的前序节点
	short_distance.put(origin, 0);
	Queue<String> queue = new LinkedList<String>();
	queue.add(origin);
	/*核心*/
	while(queue.peek() != null) {
		String node = queue.remove();
		if (routes.get(node) != null) {
			queue.addAll(routes.get(node));//取得后一列的所有元素
			for(int i = 0; i < routes.get(node).size(); i++) {
				String tnode = routes.get(node).get(i);
				int dis = distances.get(node).get(i);
				if (!short_distance.containsKey(tnode)) {
					short_routes.put(tnode, node);
					short_distance.put(tnode, short_distance.get(node) + dis);
				}else {
					if (short_distance.get(node) + dis < short_distance.get(tnode)) {
						short_distance.put(tnode, short_distance.get(node) + dis);
						short_routes.put(tnode, node);
					}
				}
			}
		}
	}
	LinkedList<String> route = new LinkedList<>();
	route.add(destination);
	/*核心*/
	while (short_routes.get(route.peekLast()) != origin) {
		route.add(short_routes.get(route.peekLast()));//找出最短路径
	}
	route.add(origin);		
	return route;
}

3.6.4 时间复杂度

Θ(m2)