单源最短路径算法Dijkstra

本题需要用到单源最短路径算法Dijkstra，现在让我们回顾该算法，其主要思想是贪心。

将所有节点分成两类：已确定从起点到当前点的最短路长度的节点，以及未确定从起点到当前点的最短路长度的节点（下面简称「未确定节点」和「已确定节点」）。

每次从「未确定节点」中取一个与起点距离最短的点，将它归类为「已确定节点」，并用它「更新」从起点到其他所有「未确定节点」的距离。直到所有点都被归类为「已确定节点」。

用节点 A「更新」节点 B 的意思是，用起点到节点 AA的最短路长度加上从节点 A 到节点 B 的边的长度，去比较起点到节点 B 的最短路长度，如果前者小于后者，就用前者更新后者。这种操作也被叫做「松弛」。

这里暗含的信息是：每次选择「未确定节点」时，起点到它的最短路径的长度可以被确定。

可以这样理解，因为我们已经用了每一个「已确定节点」更新过了当前节点，无需再次更新（因为一个点不能多次到达）。而当前节点已经是所有「未确定节点」中与起点距离最短的点，不可能被其它「未确定节点」更新。所以当前节点可以被归类为「已确定节点」。

/**
 * LeetCode 743 网络延迟时间
 * 有 n 个网络节点，标记为1到 n。
 * 给你一个列表times，表示信号经过 有向 边的传递时间。times[i] = (ui, vi, wi)，
 * 其中ui是源节点，vi是目标节点， wi是一个信号从源节点传递到目标节点的时间。
 * 现在，从某个节点K发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回-1 。
 *
 *
 * 执行结果：通过
 * 执行用时：34 ms, 在所有 Java 提交中击败了5.33%的用户
 * 内存消耗：44.9 MB, 在所有 Java 提交中击败了75.45%的用户
 * 通过测试用例：52 / 52
 *
 */
public class NetworkDelayTime {

    public int networkDelayTime(int[][] times, int n, int k) {
        int result = Integer.MIN_VALUE;
        Graph graph = convert(times);
        HashSet<Node> selectNode = new HashSet<>();
        HashMap<Node, Integer> distanceMap = new HashMap<>();
        distanceMap.put(graph.nodes.get(k), 0);
        Node minNode = getMinNodeFromDistanceMapAndUnSelectNode(distanceMap, selectNode);
        while (minNode != null) {
            Integer distance = distanceMap.get(minNode);
            for (Edge edge : minNode.edges) {
                if (!distanceMap.containsKey(edge.to)) {
                    distanceMap.put(edge.to, distance + edge.weight);
                }
                distanceMap.put(edge.to, Math.min(distanceMap.get(edge.to), distance + edge.weight));
            }
            selectNode.add(minNode);
            minNode = getMinNodeFromDistanceMapAndUnSelectNode(distanceMap, selectNode);
        }
        if (distanceMap.size() < n) {
            return -1;
        } else {
            for (Integer val : distanceMap.values()) {
                result = Math.max(val,result);
            }
            return result;
        }
    }


    public Node getMinNodeFromDistanceMapAndUnSelectNode(HashMap<Node, Integer> distanceMap, HashSet<Node> selectNode) {
        int distance = Integer.MAX_VALUE;
        Node node = null;
        for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
            if ((distance > entry.getValue()) && (!selectNode.contains(entry.getKey()))) {
                distance = entry.getValue();
                node = entry.getKey();
            }
        }
        return node;
    }

    public Graph convert(int[][] times) {
        Graph graph = new Graph();
        for (int i = 0; i < times.length; i++) {
            int from = times[i][0];
            int to = times[i][1];
            int weight = times[i][2];
            if (!graph.nodes.containsKey(from)) {
                Node node = new Node(from);
                graph.nodes.put(from, node);
            }
            if (!graph.nodes.containsKey(to)) {
                Node node = new Node(to);
                graph.nodes.put(to, node);
            }
            Edge edge = new Edge(weight, graph.nodes.get(from), graph.nodes.get(to));
            Node fromNode = graph.nodes.get(from);
            fromNode.edges.add(edge);
        }
        return graph;
    }

    public class Node {
        public int val;
        public ArrayList<Edge> edges;

        public Node() {
        }

        public Node(int val) {
            this.val = val;
            this.edges = new ArrayList<Edge>();
        }
    }

    public class Edge {
        public int weight;
        public Node from;
        public Node to;

        public Edge() {
        }

        public Edge(int weight, Node from, Node to) {
            this.weight = weight;
            this.from = from;
            this.to = to;
        }
    }

    public class Graph {
        public HashMap<Integer, Node> nodes;
        public HashSet<Edge> edges;

        public Graph() {
            this.nodes = new HashMap<Integer, Node>();
            this.edges = new HashSet<Edge>();
        }
    }
}