网站建设沛宣,如何优化网页加载速度,wordpress如何设置301,一起看地图app下载手机版如图#xff0c;设定源点为D#xff0c;终点为A#xff0c;则D到A的最短路径是多少#xff1f; 算法思路#xff1a;
第一步#xff0c;从源点D出发#xff0c;此时能到达的选择是C和E#xff0c;我们根据路径长度选择最少的作为下一个节点#xff0c;于是选择C…
如图设定源点为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;//当前节点名称MapString, 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);}}
用到全局变量存储信息方法里传递这些也行就是不好看
MapString, Node map new HashMap();//节点对象map
MapString, Boolean sign new HashMap();//节点标记
ListString 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 startD;//源节点
String endA;//目标节点
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 MapString, Node map new HashMap();//节点信息public static MapString, Boolean sign new HashMap();//防止重复计算public static ListString 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;//当前节点名称MapString, 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);}
}
