Comparison between standard Dijlstra and BFS solution, kind for beginners.
The goal is to compute the shorhest path from one single node to all nodes in directed weighted graph.\nWe can do this in both Dijlstra\'s Algorithm and BFS. \n
The goal is to compute the shorhest path from one single node to all nodes in directed weighted graph.\nWe can do this in both Dijlstra\'s Algorithm and BFS. \nMy solution is not the quickest, but it\'s easy to understand and standard. \nFor Dijlstra: \n1. put node number and temporary distance into priority queue. \n2. distance array is used to store the final result\n3. Visited array needs to be used to mark the visited nodes\n\nFor BFS: \n1. put node number into queue\n2. distance array is used to store the temporary result, updated during BFS search\n3. No need to track visited nodes\n\nSolution one: Dijlstra\'s Algorithm (26ms, faster than 74.68%)\n```\nclass intComparator implements Comparator<int[]>{\n    @Override\n    public int compare(int[] o1, int[] o2){\n        return o1[1] - o2[1];\n    }\n}\nclass Solution {\n    public int networkDelayTime(int[][] times, int N, int K) {\n        \n        //build graph\n        Map<Integer, List<List<Integer>>> map = new HashMap<>();\n        for (int[] time : times) {\n            if (!map.containsKey(time[0])) {\n                map.put(time[0], new ArrayList<>());\n            }\n            List<Integer> temp = new ArrayList<>();\n            temp.add(time[1]);\n            temp.add(time[2]);\n            map.get(time[0]).add(temp);\n        }\n        \n        //visited array + distance array + priority queue\n        boolean[] visited = new boolean[N];\n        int[] dists = new int[N];\n        Arrays.fill(dists, -1);\n        PriorityQueue<int[]> pq = new PriorityQueue<>(new intComparator());\n        //<current node number, temporary distance>\n        pq.offer(new int[] {K, 0});\n        \n        while (!pq.isEmpty()) {\n            int[] cur = pq.poll();\n            //when one node is polled out from queue\n            //the temporary distance is the final result\n            if (visited[cur[0] - 1]) continue;\n            dists[cur[0] - 1] = cur[1];\n            visited[cur[0] - 1] = true;\n            if (map.containsKey(cur[0])) {\n                List<List<Integer>> nodes = map.get(cur[0]);\n                for (List<Integer> node : nodes) {\n                    if (visited[node.get(0) - 1]) continue;\n                    pq.offer(new int[] {node.get(0), dists[cur[0] - 1] + node.get(1)});\n                }\n            }\n        }\n        int maxPath = 0;\n        for (int i = 0; i < dists.length; i ++) {\n            if (dists[i] == -1) {\n                return -1;\n            } \n            maxPath = Math.max(maxPath, dists[i]);\n        }\n        return maxPath;\n    }\n}\n```\nSolution two: BFS (27ms, faster than 73.78%)\n```\nclass Solution {\n    public int networkDelayTime(int[][] times, int N, int K) {\n        // build graph\n        Map<Integer, List<List<Integer>>> map = new HashMap<>();\n        for (int[] time : times) {\n            if (!map.containsKey(time[0])) {\n                map.put(time[0], new ArrayList<>());\n            }\n            List<Integer> temp = new ArrayList<>();\n            temp.add(time[1]);\n            temp.add(time[2]);\n            map.get(time[0]).add(temp);\n        }\n        \n        //dists array to keep temporary results, needs to be updated during bfs\n        int[] dists = new int[N];\n        Arrays.fill(dists, Integer.MAX_VALUE);\n        Queue<Integer> q = new LinkedList<>();\n        q.offer(K);\n        dists[K - 1] = 0;\n        while (!q.isEmpty()) {\n            int cur = q.poll();\n            int dist = dists[cur - 1];\n            if (map.containsKey(cur)) {\n                List<List<Integer>> nodes = map.get(cur);\n                for (List<Integer> node : nodes) {\n                    //update dists\n                    if (dists[node.get(0) - 1] <= dist + node.get(1)) continue;\n                    dists[node.get(0) - 1] = dist + node.get(1);\n                    q.offer(node.get(0));\n                }\n            }\n        }\n        int maxPath = 0;\n        for (int i = 0; i < dists.length; i ++) {\n            if (dists[i] == Integer.MAX_VALUE) {\n                return -1;\n            } \n            maxPath = Math.max(maxPath, dists[i]);\n        }\n        return maxPath;\n    }\n}\n```
['Breadth-First Search', 'Java']