随笔记录

图-最短路径-Dijkstra算法

2022-4-14 diaba 算法

package com.jiucaiyuan.net.algrithm.graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * Dijkstra算法
 * 适用于：可以有权值为负数的边，但是不能有累加为负数的环的无向图，指定一个出发点，计算到所有节点的最短路径算法
 *
 * @Author jiucaiyuan  2022/4/14 21:36
 * @mail services@jiucaiyuan.net
 */

public class Dijkstra {
    /**
     * 迪杰斯特拉算法 Dijkstra算法，从指定节点出发，到图中所有节点的最短距离的计算
     *
     * @param head 图中指定出发的节点
     * @return 返回从head出发，到图中所有节点的最短距离
     */
    public static HashMap<Node, Integer> dijkstra(Node head) {
        //从 head 出发到当前点的最小距离
        //key 从 head 出发到达当前节点
        //value 从head出发到达节点的最小值
        //如果在表中，没有T的记录，含义是从head出发到达T的j距离为正无穷
        HashMap<Node, Integer> distanceMap = new HashMap<>();
        distanceMap.put(head, 0);
        //已经求过距离的节点，存放到 selectedNodes 中，以后再也不碰了
        Set<Node> selectedNodes = new HashSet<>();
        //这里返回的应该是head节点
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        while (minNode != null) {
            //获取到 minNode 节点的距离
            int distance = distanceMap.get(minNode);
            //从 minNode 出发所有边的距离
            for (Edge edge : minNode.edges) {
                Node toNode = edge.to;
                //从当前节点minNode往外跳，到toNode节点的新距离
                int newDistance = distance + edge.weight;
                if (!distanceMap.containsKey(toNode)) {
                    //如果这个节点还没有处理过
                    distanceMap.put(toNode, newDistance);
                } else {
                    //当前得到的距离和之前的距离相比，如果更短了，更新距离
                    distanceMap.put(toNode, Math.min(distanceMap.get(toNode), newDistance));
                }
            }
            selectedNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        }
        return distanceMap;
    }

    /**
     * 从 distanceMap 中找到最小的距离对应的节点，该节点不能在指定的 excludeNodes 中
     *
     * @param distanceMap  到 key 这个节点最小距离集合
     * @param excludeNodes 找的最短距离的节点不能出现在这里（已选取过了）
     * @return 最短距离的 node
     */
    private static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, Set<Node> excludeNodes) {
        //最小距离的节点
        Node minNode = null;
        //记录最小距离
        int minDistance = Integer.MAX_VALUE;
        for (Node currNode : distanceMap.keySet()) {
            int distance = distanceMap.get(currNode);
            if (!excludeNodes.contains(currNode) && distance < minDistance) {
                minNode = currNode;
                minDistance = distance;
            }
        }
        return minNode;
    }
}