迪杰斯特拉算法

迪杰斯特拉算法

import java.util.ArrayList;import java.util.HashMap;import java.util.HashSet;import java.util.Map;/** * 迪杰斯特拉算法(Dijkstra)是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题(权重必须不能为负)。 * 迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止 */public class Dijkstra { public static HashMap dijkstra1(Node from) { // 从head出发到所有点的最小距离 // key : 从head出发到达key // value : 从head出发到达key的最小距离 // 如果在表中，没有T的记录，含义是从head出发到T这个点的距离为正无穷 HashMap distanceMap = new HashMap<>(); distanceMap.put(from, 0); // 已经求过距离的节点，存在selectedNodes中，以后再也不碰 HashSet selectedNodes = new HashSet<>(); // from 0 Node minNode = getMinDistanceAndUnselectedNode(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 { distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight)); } } selectedNodes.add(minNode); minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes); } return distanceMap; } public static Node getMinDistanceAndUnselectedNode(HashMap distanceMap, HashSet touchedNodes) { Node minNode = null; int minDistance = Integer.MAX_VALUE; for (Map.Entry entry : distanceMap.entrySet()) { Node node = entry.getKey(); int distance = entry.getValue(); if (!touchedNodes.contains(node) && distance < minDistance) {minNode = node;minDistance = distance;}}return minNode;}// 改进后的dijkstra算法// 从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回public static HashMap dijkstra2(Node head, int size) { NodeHeap nodeHeap = new NodeHeap(size); nodeHeap.addOrUpdateOrIgnore(head, 0); HashMap result = new HashMap<>(); while (!nodeHeap.isEmpty()) { NodeRecord record = nodeHeap.pop(); Node cur = record.node; int distance = record.distance; for (Edge edge : cur.edges) { nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance); } result.put(cur, distance); } return result; } public static class NodeRecord { public Node node; public int distance; public NodeRecord(Node node, int distance) { this.node = node; this.distance = distance; } } public static class NodeHeap { private Node[] nodes; // 实际的堆结构 // key 某一个node， value 上面堆中的位置 private HashMap heapIndexMap; // key 某一个节点， value 从源节点出发到该节点的目前最小距离 private HashMap distanceMap; private int size; // 堆上有多少个点 public NodeHeap(int size) { nodes = new Node[size]; heapIndexMap = new HashMap<>(); distanceMap = new HashMap<>(); } public boolean isEmpty() { return size == 0; } // 有一个点叫node，现在发现了一个从源节点出发到达node的距离为distance // 判断要不要更新，如果需要的话，就更新 public void addOrUpdateOrIgnore(Node node, int distance) { if (inHeap(node)) { distanceMap.put(node, Math.min(distanceMap.get(node), distance)); insertHeapify(node, heapIndexMap.get(node)); } if (!isEntered(node)) { nodes[size] = node; heapIndexMap.put(node, size); distanceMap.put(node, distance); insertHeapify(node, size++); } } public NodeRecord pop() { NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0])); swap(0, size - 1); heapIndexMap.put(nodes[size - 1], -1); distanceMap.remove(nodes[size - 1]); // free C++同学还要把原本堆顶节点析构，对java同学不必 nodes[size - 1] = null; heapify(0, --size); return nodeRecord; } private void insertHeapify(Node node, int index) { while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {swap(index, (index - 1) / 2);index = (index - 1) / 2;}}private void heapify(int index, int size) {int left = index * 2 + 1;while (left < size) { int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left]) ? left + 1 : left; smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;if (smallest == index) {break;}swap(smallest, index);index = smallest;left = index * 2 + 1;}}private boolean isEntered(Node node) {return heapIndexMap.containsKey(node);}private boolean inHeap(Node node) {return isEntered(node) && heapIndexMap.get(node) != -1;}private void swap(int index1, int index2) {heapIndexMap.put(nodes[index1], index2);heapIndexMap.put(nodes[index2], index1);Node tmp = nodes[index1];nodes[index1] = nodes[index2];nodes[index2] = tmp;}}public static class Node {public int value;public int in;public int out;public ArrayList nexts; public ArrayList edges; public Node(int value) { this.value = value; nexts = new ArrayList<>(); edges = new ArrayList<>(); } } public static class Edge { // 权重 public int weight; public Node from; public Node to; public Edge(int weight, Node from, Node to) { this.weight = weight; this.from = from; this.to = to; } }}/* 如有意见或建议，欢迎评论区留言；如发现代码有误，欢迎批评指正 */

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。