外贸网站建设报价差别那么大花钱多吃亏,凡科网站投票排行榜是怎么做的,昆明排名推广,中山专业找人公司迪锐克斯拉算法 简单来说就是在有向图中#xff0c;给定一个图中具体的出发点#xff0c;从这个点出发能够到达的所有的点#xff0c;每个点的最短距离是多少。到不了的点#xff0c;距离则是正无穷。有向#xff0c;无负权重#xff0c;可以有环。 所以说#xff0c;迪…迪锐克斯拉算法 简单来说就是在有向图中给定一个图中具体的出发点从这个点出发能够到达的所有的点每个点的最短距离是多少。到不了的点距离则是正无穷。有向无负权重可以有环。 所以说迪锐克斯拉算法是生成一个从源点出发到各个点的最小距离表。 举例有向图如图所示
从给定的出发点a出发最终要获得的是a到b,c,d,e每个点之间的最短距离。默认a到自己的距离是0其他的点还没到达的点的距离是正无穷。已经确定的答案不动在没有确定的记录中找一个最小的出来。
abcde0正无穷正无穷正无穷正无穷
所以先从a点出发的三条边126。中找出权重为1的边ad距离为1小于之前的正无穷比之前距离小所以更新a到d之间的距离bcd同理。所以更新完后距离如下
abcde0261正无穷
此时从a出发的三条边已经走完所以a点确定下来再也不动。 其余没有确定的记录中d是最短的从a出发到b的距离为1所以从d开始向下找d属于中间的跳点。 d出发的边有两条分别是dc和de。其中dc距离为2再加上之前a到d的距离为1所以此时a到c的距离经过d跳转后为3小于之前的6所以更新ac之间距离同样de距离7小于正无穷。所以也进行更新。d也确定了。
abcde02317
接下来从不确定的记录中根据最小的向下找。b点出发的边有一条bebe距离9加上a到b的距离2所以be距离为11大于之前的不更新。b也确定了。
abcde02317
还剩下c从c点出发的边有两条cb和ce因为b点已经确定了不再动所以一看ce一条ce距离为3a到c距离为3所以ae之间距离为6小于之前更新e点距离。
abcde02316
代码 根据上面的分析进行代码的实现不过getMinDistanceAndUnSelectNode有瑕疵因为每找一个minNode就会在集合中都遍历一次。会在下面进行代码优化。 public static HashMapNode, Integer dijkstra1(Node from) {HashMapNode, Integer distanceMap new HashMap();distanceMap.put(from, 0);//已经确定的边HashSetNode selectedNodes new HashSet();//根据已经确定的记录 和 map找出没确定的中最小的记录Node minNode getMinDistanceAndUnSelectNode(distanceMap, selectedNodes);while (minNode ! null) {int distance distanceMap.get(minNode);for (Edge edge : minNode.edges) {Node toNode edge.to;if (!distanceMap.containsKey(toNode)) {distanceMap.put(toNode, distance edge.weight);} else {//edge.weight distance 当前边的权重 我此时当做跳点的距离。//distanceMap.get(toNode) 已经存在的距离distanceMap.put(toNode, Math.min(distanceMap.get(toNode), (edge.weight distance)));}}//所有的边都已经遍历完这个点可以确定了放到确定的集合中。selectedNodes.add(minNode);//再次获取最小的记录minNode getMinDistanceAndUnSelectNode(distanceMap, selectedNodes);}return distanceMap;}public static Node getMinDistanceAndUnSelectNode(HashMapNode, Integer distanceMap, HashSetNode selectedNode) {Node minNode null;int minDistance Integer.MAX_VALUE;for (Map.EntryNode, Integer entry : distanceMap.entrySet()) {Node node entry.getKey();int distance entry.getValue();if (!selectedNode.contains(node) distance minDistance) {minDistance distance;minNode node;}}return minNode;}
