迪杰斯特拉(Dijsktra)算法求到任意节点的最短路径

本文主要是介绍迪杰斯特拉(Dijsktra)算法求到任意节点的最短路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

迪杰斯特拉算法要求

• 1.必须给一个起点,求出起点到任何节点的最短路径,如果不可达那么距离设定为正无穷                 
• 2.输出一张表记录一个节点到任何节点的最短路径                                                                           
• 3.dijkstra本质是一种贪心算法

        要求: 不能出现权值为负的边(如果沿途路径不能构成一个环那么也可以,但最好不要有)

操作: 维护一张记录起点到任何节点的距离映射表,初始化起始点到自身距离为0,遍历该节点到其所有边可到达的最短距离并存入距离映射表,如果已存在比对存有的距离与当前距离取最小并更新距离映射表,一度完成后将该节点锁定到lockedSet中.开启下一轮,找出不存在与锁定set且距离最小的节点作为跳跃点 ...

/*** 给定一个起点返回该起点到任何节点的最短路径* @param start 起点* @return 最短路径表*/public static HashMap<Node,Integer> dijkstra(Node start){//距离表HashMap<Node,Integer> distanceMap = new HashMap<>();//只要达到距离最小即为更新完毕,进入锁定的集合中,避免重复更新HashSet<Node> lockedNode = new HashSet<>();//起始节点距离自身距离为0,未进入的节点说明此时距离为 + ∞distanceMap.put(start,0);//对未完成更新的节点进行距离更新Node minNode

这篇关于迪杰斯特拉(Dijsktra)算法求到任意节点的最短路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---