动态规划解决最短路径问题_动态规划求最短路径问题

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 代码实现

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
1
2