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;

    }

}