最短路径问题

如图，设定源点为D，终点为A，则D到A的最短路径是多少？

 算法思路：

第一步，从源点D出发，此时能到达的选择是C和E，我们根据路径长度选择最少的作为下一个节点，于是选择C，

第二步，到达C后，标记C已经走过了，后续再做选择时，排除C。然后将所有C能到达的节点告知D，也就是B、F、E。由D来分辨，B、F、E这些点，是通过C节点路最短，还是D现有方案最短。选择最短的方案记录下来。然后选择B、F、E中C节点最近的、没标记过的节点作为下一步。

第三步，重复第二步操作，直到选不到下一个节点而结束。

考虑特殊的情况，假如图不是闭环的，这个方式可能会被引导在断路的地方停止。于是记录走过的路，当找不到路的时候，确认end没有找到，且还有节点没被标记的情况下，退回上一个路口。

（1）如果节点都被标记或者已经找到终点了，就退出

（2）如果还有节点未被标记可以回退上一次选择的地方继续选择。

最后直接询问源节点D中对于终点A的方案是什么，最短路径是多少。

代码：

封装图中的节点

   class Node {String name;//当前节点名称Map<String, Integer> path = new HashMap<>();//目标节点->最短路径public Node(String name) { this.name = name; }/*** 更新到达某个节点的最短路径* @param name 目标节点* @param len 最短路径*/public void update(String name, int len) {path.put(name, len);}/*** 获取指定节点的最短路径* @param name 目标节点* @return 最短路径*/public int getLen(String name) {return path.getOrDefault(name, Integer.MAX_VALUE);}}

用到全局变量存储信息，方法里传递这些也行，就是不好看

Map<String, Node> map = new HashMap<>();//节点对象map
Map<String, Boolean> sign = new HashMap<>();//节点标记
List<String> list = new ArrayList<>();//记录走的路径，处理碰到死路的情况，可以退上一个节点

初始化代码，将图上的数据跑入节点对象中。

Object[][] params = {{"A", "B", 12},{"A", "F", 16},{"A", "G", 14},{"B", "F", 7},{"B", "C", 10},{"C", "F", 6},{"C", "E", 5},{"C", "D", 3},{"D", "E", 4},{"E", "F", 2},{"E", "G", 8},{"F", "G", 9}
};
//导入路径数据
for(Object[] p:params){if(!map.containsKey((String)p[0]))map.put((String)p[0],new Node((String) p[0]));if(!map.containsKey((String)p[1]))map.put((String)p[1],new Node((String) p[1]));map.get((String)p[0]).update((String)p[1],(int)p[2]);map.get((String)p[1]).update((String)p[0],(int)p[2]);
}

开始算法

    /*** 选择它下面最小路径出发，更新自己到达最近节点位置** @param name*/boolean f(String name, Node start, String end) {Node now = map.get(name);//获取节点实体sign.put(name, true);//标记已经走过了list.add(name);/*** 更新源节点对能到达节点的最短路径，当前节点是源节点的时候不用更新*/if (!name.equals(start.name)) {int nowLen = start.getLen(name);//取出源节点到当前节点的最短路径,用于后续计算for (String key : now.path.keySet()) {//取出当前节点能直达的所有节点if (!key.equals(start.name)) {//将当前节点到达每一个节点的路径信息告知给到源节点，让源节点扩充自己的最短路径数据int newNodeLen = now.getLen(key) + nowLen;//源节点到新节点的路径长度if (start.getLen(key) > newNodeLen) { //源节点取出原有方案，对比，保留最短的方案start.update(key, newNodeLen);map.get(key).update(start.name, newNodeLen);//路径双方都更新}}}}String nextName = getNextName(now,end);if (nextName == null) return true;return f(nextName, start, end);}

里面涉及到选择最近节点的方法以及包含死路的时候回退操作，

    /*** 获取下一个路径节点* @param now* @param end* @return*/public static String getNextName(Node now,String end){String nextName = null;int min = Integer.MAX_VALUE;for (String key : now.path.keySet()) {if (sign.containsKey(key) && sign.get(key)) continue;if (now.getLen(key) < min) {min = now.getLen(key);nextName = key;}}if (nextName == null) {if (sign.containsKey(end) && sign.get(end)) return null;}else{return nextName;}list.remove(list.size()-1);return getNextName(map.get(list.get(list.size()-1)),end);}

最后使用上面这些东西

String start="D";//源节点
String end="A";//目标节点
f(start, map.get(start), end);
System.out.println(map.get(start).getLen(end));

无脑完整代码：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;public class Main {public static Map<String, Node> map = new HashMap<>();//节点信息public static Map<String, Boolean> sign = new HashMap<>();//防止重复计算public static List<String> list = new ArrayList<>();//记录走的路径，处理碰到死路的情况，可以退上一个节点public static void main(String[] args) {init();//初始化数据String start = "D";//源节点String end = "A";//目标节点f(start, map.get(start), end);//算法寻找System.out.println(map.get(start).getLen(end));//拿出来始终节点的最短路径}/*** 初始化数据*/public static void init(){Object[][] params = {{"A", "B", 12},{"A", "F", 16},{"A", "G", 14},{"B", "F", 7},{"B", "C", 10},{"C", "F", 6},{"C", "E", 5},{"C", "D", 3},{"D", "E", 4},{"E", "F", 2},{"E", "G", 8},{"F", "G", 9}};//导入路径数据for (Object[] p : params) {if (!map.containsKey((String) p[0])) map.put((String) p[0], new Node((String) p[0]));if (!map.containsKey((String) p[1])) map.put((String) p[1], new Node((String) p[1]));map.get((String) p[0]).update((String) p[1], (int) p[2]);map.get((String) p[1]).update((String) p[0], (int) p[2]);}}/*** 选择它下面最小路径出发，更新自己到达最近节点位置** @param name*/public static boolean f(String name, Node start, String end) {Node now = map.get(name);//获取节点实体sign.put(name, true);//标记已经走过了list.add(name);/*** 更新源节点对能到达节点的最短路径，当前节点是源节点的时候不用更新*/if (!name.equals(start.name)) {int nowLen = start.getLen(name);//取出源节点到当前节点的最短路径,用于后续计算for (String key : now.path.keySet()) {//取出当前节点能直达的所有节点if (!key.equals(start.name)) {//将当前节点到达每一个节点的路径信息告知给到源节点，让源节点扩充自己的最短路径数据int newNodeLen = now.getLen(key) + nowLen;//源节点到新节点的路径长度if (start.getLen(key) > newNodeLen) { //源节点取出原有方案，对比，保留最短的方案start.update(key, newNodeLen);map.get(key).update(start.name, newNodeLen);//路径双方都更新}}}}String nextName = getNextName(now,end);if (nextName == null) return true;return f(nextName, start, end);}/*** 获取下一个路径节点* @param now* @param end* @return*/public static String getNextName(Node now,String end){String nextName = null;int min = Integer.MAX_VALUE;for (String key : now.path.keySet()) {if (sign.containsKey(key) && sign.get(key)) continue;if (now.getLen(key) < min) {min = now.getLen(key);nextName = key;}}if (nextName == null) {if (sign.containsKey(end) && sign.get(end)) return null;}else{return nextName;}list.remove(list.size()-1);return getNextName(map.get(list.get(list.size()-1)),end);}
}
class Node {String name;//当前节点名称Map<String, Integer> path = new HashMap<>();//目标节点->最短路径public Node(String name) {this.name = name;}/*** 更新到达某个节点的最短路径** @param name 目标节点* @param len  最短路径*/public void update(String name, int len) {path.put(name, len);}/*** 获取指定节点的最短路径** @param name 目标节点* @return 最短路径*/public int getLen(String name) {return path.getOrDefault(name, Integer.MAX_VALUE);}
}