Network Delay Time — Leetcode 743

Original problem link: https://leetcode.com/problems/network-delay-time/description/

In this problem, we are given a weighted directed graph representing a network and we are given a number of nodes n and a starting node k for sending a signal from. All nodes are labeled 1 to n. We are asked to return the minimum time it takes for all nodes to get the signal (-1 if that is impossible).

This is a graph search problem, but it’s not quite the same as just visiting every vertex once in the order we see them in because a subsequent path may be smaller. Thus, there is a bit of a modification in the neighbors loop inside the queue loop.

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, Set<Pair<Integer, Integer>>> graph = new HashMap<>();
        for (int[] edge : times) {
            if (graph.containsKey(edge[0])) {
                graph.get(edge[0]).add(new Pair(edge[1], edge[2]));
            } else {
                Set<Pair<Integer, Integer>> neighbors = new HashSet<>();
                neighbors.add(new Pair(edge[1], edge[2]));
                graph.put(edge[0], neighbors);
            }
        }

        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(k);
        int[] visited = new int[n];
        Arrays.fill(visited, -1);
        visited[k - 1] = 0;
        while (!queue.isEmpty()) {
            int vertex = queue.poll();  
            int time = visited[vertex - 1];

            Set<Pair<Integer, Integer>> neighbors = graph.getOrDefault(vertex, new HashSet<>());
            for (Pair<Integer, Integer> pair : neighbors) {
                int neighbor = pair.getKey();
                int weight = pair.getValue();

                if (visited[neighbor - 1] == -1) {
                    visited[neighbor - 1] = time + weight;
                    queue.add(neighbor);
                } else {
                    if (visited[neighbor - 1] > time + weight) {
                        // subsequent path is smaller, so we need to modify the queue order
                        visited[neighbor - 1] = time + weight;
                        queue.remove(neighbor);
                        queue.add(neighbor);
                    }
                }
            }
        }

        int result = 0;
        for (int time : visited) {
            if (time == -1) {
                return -1;
            }
            result = Math.max(result, time);
        }
        return result;
    }
}

This solution beats 77% of submissions at 20 ms of runtime.