dijkstral算法详解

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;public class test39 {// 定义节点类，表示图中的顶点public static class Node {public int value; // 节点的值，即编号public int in; // 进入该节点的边的数量public int out; // 从该节点出去的边的数量public ArrayList<Node> nexts; // 直接邻居，由当前节点出发能到达的节点列表public ArrayList<Edge> edges; // 与该节点相关的边的集合public Node(int value) {this.value = value;in = 0;out = 0;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;}}// 定义图类，包含节点和边的集合public static class Graph {public HashMap<Integer, Node> nodes; // 存储图中所有节点的映射，键为节点编号，值为节点对象public HashSet<Edge> edges; // 存储图中所有边的集合public Graph() {nodes = new HashMap<>();edges = new HashSet<>();}}// 根据二维数组创建图结构的方法public static Graph createGraph(Integer[][] matrix) {Graph graph = new Graph();for (int i = 0; i < matrix.length; i++) {// 获取权重、起始点和终止点的值Integer weight = matrix[i][0];Integer from = matrix[i][1];Integer to = matrix[i][2];// 如果图中没有起始点，则新建一个节点并添加到图中if (!graph.nodes.containsKey(from)) {graph.nodes.put(from, new Node(from));}// 如果图中没有终止点，则新建一个节点并添加到图中if (!graph.nodes.containsKey(to)) {graph.nodes.put(to, new Node(to));}// 获取起始点和终止点的节点对象Node fromNode = graph.nodes.get(from);Node toNode = graph.nodes.get(to);// 创建一条新的边并将其添加到图中Edge newEdge = new Edge(weight, fromNode, toNode);// 更新起始点和终止点的邻居列表和边的数量fromNode.nexts.add(toNode);fromNode.out++;toNode.in++;fromNode.edges.add(newEdge);graph.edges.add(newEdge);}return graph;}// Dijkstra算法实现，计算从指定起点到其他所有点的最短路径长度public static HashMap<Node, Integer> dijkstral(Node from) {HashMap<Node, Integer> distanceMap = new HashMap<>(); // 存储每个节点到起点的距离distanceMap.put(from, 0); // 起点到自己的距离为0HashSet<Node> selectNodes = new HashSet<>(); // 存储已经处理过的节点Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectNodes); // 获取未处理的节点中距离最小的节点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));}}selectNodes.add(minNode); // 将当前节点标记为已处理minNode = getMinDistanceAndUnselectedNode(distanceMap, selectNodes); // 获取下一个未处理的节点中距离最小的节点}return distanceMap; // 返回所有节点到起点的最短距离映射表}// 辅助方法：获取未处理的节点中距离最小的节点public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) {Node minNode = null; // 初始化最小距离节点为nullint minDistance = Integer.MAX_VALUE; // 初始化最小距离为最大整数值for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) { // 遍历距离映射表Node node = entry.getKey(); // 获取节点int distance = entry.getValue(); // 获取节点到起点的距离if (!touchedNodes.contains(node) && distance < minDistance) { // 如果节点未处理且距离小于当前最小距离minNode = node; // 更新最小距离节点minDistance = distance; // 更新最小距离}}return minNode; // 返回最小距离节点}
}