743. Network Delay Time

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {

        // TODO: create a map representing the distance from the source node to any other node.
        // map.get(x) means the distance from node k -> x. Therefore k -> k = 0
        Map<Integer, Integer> dist = new HashMap<>();
        for (int i = 1; i <= n; i ++) {
            dist.put(i, Integer.MAX_VALUE);
        }
        dist.put(k, 0);

        // TODO: a map represent the graph. with graph.get(x) shows another map storing the adjacent nodes and the weights of the edge.
        // So if graph.get(x).get(y) = w, then the weight of edge x -> y is w.
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (int[] edge: times) {
            int source = edge[0];
            int dest = edge[1];
            int weight = edge[2];
            graph.putIfAbsent(source, new HashMap<>());
            graph.get(source).put(dest, weight);
        }

        // start BFS
        Queue<Integer> bfs = new LinkedList<>();
        bfs.add(k);

        while (!bfs.isEmpty()) {
            int top = bfs.remove();
            if (!graph.containsKey(top)) {
                continue;
            }
            for (int adjNode: graph.get(top).keySet()) {
                int newValue = dist.get(top) + graph.get(top).get(adjNode);
                if (newValue < dist.get(adjNode)) {
                    bfs.add(adjNode);
                    dist.put(adjNode, newValue);
                }
            }
        }


        // TODO: check the max value
        int max = 0;
        for (int node: dist.keySet()) {
            if (dist.get(node) == Integer.MAX_VALUE) {
                return -1;
            }
            max = Math.max(max, dist.get(node));
        }
        return max;
    }
}

class Solution {
    class Node {
        int nodeIdx;
        int value;

        Node(int nodeIdx, int value) {
            this.nodeIdx = nodeIdx;
            this.value = value;
        }
    }
    public int networkDelayTime(int[][] times, int n, int k) {
        /*
        Find the shortest path from a single source in a directed graph.

        1. Check if there is a cycle? Maybe yes
        2. All weights are positive
        3. times.length = 6000

        We might be able to use Dijkstra to solve this problem

        Start with a node:
        - relax the adjacent node
        - repeat the project until all nodes are visited
        - return the one with the maximum value so far.

        Implement:
        1. Have a map to keep track of the distance from the source to the current node

        map[a]: int => dist from source to a

        map[b] can be : Math.min(map[b], map[c] + dist(c, b))

        2. Have a map to store the distance between the nodes. Since this is directed edges, we just need to do it for 1 way

        3. Initialize a Priority Queue for retrieve the3 values of the smallest edge. How to

        If at somepoint, the priority queue is empty but not all nodes are visited, return -1. Otherwise, return the max value so far => store the max value 
        */
        Map<Integer, Integer> distFromSource = new HashMap<>();
        // one obvious initial
        for (int i = 1; i <= n; i++) {
            distFromSource.put(i, Integer.MAX_VALUE);
        }
        distFromSource.put(k, 0);


        Map<Integer, Map<Integer, Integer>> graphRepresent = new HashMap<>();

        // to store the edge and weight
        for (int[] edge: times) {
            int source = edge[0];
            int dest = edge[1];
            int weight = edge[2];
            graphRepresent.putIfAbsent(source, new HashMap<>());
            graphRepresent.get(source).put(dest, weight);
        }

        // start the Dijkstra
        int maxValue = 0;
        PriorityQueue<Node> dijkstra = new PriorityQueue<>((a, b) -> (a.value - b.value));
        Set<Integer> visited = new HashSet<>();

        dijkstra.add(new Node(k, 0));
        visited.add(k);

        while (!dijkstra.isEmpty() && visited.size() < n) {
            Node node = dijkstra.remove();
            maxValue = Math.max(maxValue, node.value);
            visited.add(node.nodeIdx);
            // go through the adjacent nodes to do the relaxing part

            if (!graphRepresent.containsKey(node.nodeIdx)) {
                continue;
            }
            for (int adjNode: graphRepresent.get(node.nodeIdx).keySet()) {
                if (!visited.contains(adjNode)) {
                    int newValue = distFromSource.get(node.nodeIdx) + graphRepresent.get(node.nodeIdx).get(adjNode);
                    if (newValue < distFromSource.get(adjNode)) {
                        distFromSource.put(adjNode, newValue);
                        dijkstra.add(new Node(adjNode, newValue));
                    }

                }
            }
        }

        if (visited.size() < n) {
            return -1;
        }

        return maxValue;
    }
}