Java | Dijkstra's algorithm & Fibonacci Heap explained
This question is a classic example for using Dijkstra\'s single-source shortest path finiding algorithm. But why is that?\n\nIntuition\nThe problem statement ma
This question is a classic example for using Dijkstra\'s single-source shortest path finiding algorithm. But why is that?\n\n**Intuition**\nThe problem statement makes it clear that this is a graph problem, all we need to do is to decied which algorithm to use in order to solve it.\nSince we are dealling with weighted edges, *BFS* will not work here (unless all weights were equal, which really mean no weights at all).\n*DFS* won\'t cut it too (even if we wouldn\'t have any weights), since it doesn\'t find the shortest path.\nYou can use *Bellman-Ford* for this question, however it won\'t be optimal and it doesn\'t necessary given that all weights are positive integers (which is a classic hint for using Dijkstra).\nAnother option is *Floyd-Warshall*, but it isn\'t necessary either given that we have a single source.\n\nAfter we decided to use Dijkstra, we just need to add the functionality of tracking the longest path in the graph - which is the answer.\n\n**Fibonacci Heap**\nIf you pay close attention you would notice that in the worst case our heap will have O(E) nodes in it. Since we never poll out outdated paths from our heap and only offering new ones. That means we pay O(logE) for each heap.offer() call. A standard Priority Queue doesn\'t have the functionality of decreasing a key value. This is where Fibonacci heaps comes into play. Fibonacci Heaps have a decreasePriority in O(logN) where N is the heap size. With that we can secure the promise of O(ElogV) for Dijksta\'s algorithm.\nI haven\'t used Fibonacci Heap in my solution because the standard Java collections API does not contain an implementation of it, and implementing it during a real interview will be an overkill for this type of question. However I would definitely mention it. \n\n**Algorithm**\n```\nclass Solution {\n    public int networkDelayTime(int[][] times, int N, int K) {\n        Map<Integer, List<int[]>> adjacencyMap = new HashMap<>();\n        for (int[] edge : times) {\n            adjacencyMap.putIfAbsent(edge[0], new ArrayList<>());\n            adjacencyMap.get(edge[0]).add(new int[]{edge[1], edge[2]});\n        }\n        \n        Queue<int[]> heap = new PriorityQueue<>(\n            (e1, e2) -> Integer.compare(e1[1], e2[1]));\n        heap.offer(new int[]{K, 0});\n        Map<Integer, Integer> distanceByNode = new HashMap<>();\n        \n        int elapsedTime = 0;\n        while (!heap.isEmpty()) {\n            int[] current = heap.poll();\n            int node = current[0], distance = current[1];\n            if (distanceByNode.containsKey(node)) continue;\n            elapsedTime = Math.max(elapsedTime, distance);\n            distanceByNode.put(node, distance);\n            if (!adjacencyMap.containsKey(node)) continue;\n            for (int[] edge : adjacencyMap.get(node)) {\n                int neighbour = edge[0], weight = edge[1];\n                if (distanceByNode.containsKey(neighbour)) continue;\n                heap.offer(new int[]{neighbour, distance+weight});\n            }\n        }\n        return distanceByNode.size() != N ? -1 : elapsedTime;\n    }\n}\n```
['Heap (Priority Queue)', 'Java']