Shortest Path Faster Algorithm (SPFA) - Java 26ms beats 86.85%
SPFA is an improvement on top of Bellman-Ford, and prabably easier to understand than Dijkstra.  It is popular with students who take part in NOIP and ACM-ICPC.
SPFA is an improvement on top of Bellman-Ford, and prabably easier to understand than Dijkstra.  It is popular with students who take part in NOIP and ACM-ICPC. The key points are\n1. We use a FIFO queue to store vertices that are about to be relaxed.\n2. Vertices should be reinserted into the queue whenever its distance is updated.\n\nAs claimed in wikipedia https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm the worst case comlexity is the same as Bellman-Ford, but the average running time is O(|E|) .\n```\n    public int networkDelayTime(int[][] times, int N, int K) {\n        // construct the graph\n        Map<Integer, Map<Integer, Integer>> costs = new HashMap<>();\n        for (int[] e: times) {\n            costs.putIfAbsent(e[0], new HashMap<Integer, Integer>());\n            costs.get(e[0]).put(e[1], e[2]);\n        }\n        \n        int[] distances = new int[N+1];\n        Arrays.fill(distances, Integer.MAX_VALUE);\n        distances[K] = 0;\n        \n        Queue<Integer> que = new LinkedList<>();\n        boolean[] inQue = new boolean[N+1]; // indicate whether the element is inside the queue or not\n        que.offer(K);\n        while (!que.isEmpty()) {\n            int node = que.poll();\n            inQue[node] = false;\n            if (!costs.containsKey(node)) continue;\n            for (int next: costs.get(node).keySet()) {\n                int d = costs.get(node).get(next);\n                if (distances[next] > distances[node] + d) {\n                    distances[next] = distances[node] + d;\n                    if (!inQue[next]) {\n                        que.offer(next);\n                        inQue[next] = true;\n                    }\n                }\n            }\n        }\n        \n        int result = 0;\n        for (int i = 1; i <= N; i++) {\n            result = Math.max(result, distances[i]); \n        }\n        \n        return result == Integer.MAX_VALUE ? -1 : result;\n    }\n```
[]