Dijkstra's Algorithm - Template - List of Problems
Dijlstra\'s Algorithm\n\n743. Network Delay Time\n\n\n/*\nStep 1: Create a Map of start and end nodes with weight\n        1 -> {2,1},{3,2}\n        2 -> {4,4},
Dijlstra\'s Algorithm\n\n**743. Network Delay Time**\n\n```\n/*\nStep 1: Create a Map of start and end nodes with weight\n        1 -> {2,1},{3,2}\n        2 -> {4,4},{5,5}\n        3 -> {5,3}\n        4 ->\n        5 ->\n\nStep 2: create a result array where we will keep track the minimum distance to rech end of the node from start node\n\nStep 3: Create a Queue and add starting position with it\'s weight and add it\'s reachable distance with increament of own\'t weight plus a weight require to reach at the end node from start node.\n        We keep adding and removing pairs from queue and updating result array as well.\n\nStep 4: find the maximum value from result array:\n\n*/\n\nclass Solution {\n    public int networkDelayTime(int[][] times, int n, int k) {\n        \n        //Step 1\n        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();\n        \n        for(int[] time : times) {\n            int start = time[0];\n            int end = time[1];\n            int weight = time[2];\n            \n            map.putIfAbsent(start, new HashMap<>());\n            map.get(start).put(end, weight);\n        }\n        \n         // Step 2\n        int[] dis = new int[n+1];\n        Arrays.fill(dis, Integer.MAX_VALUE);\n        dis[k] = 0;\n        \n        Queue<int[]> queue = new LinkedList<>();\n        queue.add(new int[]{k,0});\n        \n        //Step 3:\n        while(!queue.isEmpty()) {\n            int[] cur = queue.poll();\n            int curNode = cur[0];\n            int curWeight = cur[1];\n            \n            for(int next : map.getOrDefault(curNode, new HashMap<>()).keySet()) {\n                int nextweight = map.get(curNode).get(next);\n                \n                if(curWeight + nextweight < dis[next]) {\n                    dis[next] = curWeight + nextweight;\n                    queue.add(new int[]{next, curWeight + nextweight});\n                }\n            }\n        }\n        \n        //Step 4:\n        int res = 0;\n        for(int i=1; i<=n; i++) {\n            if(dis[i] > res) {\n                res = Math.max(res, dis[i]);\n            } \n        }\n        \n        return res == Integer.MAX_VALUE ? -1 : res;\n    }\n}\n\n```\n\n**1514. Path with Maximum Probability**\n\n```\nclass Solution {\n    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {\n        Map<Integer, Map<Integer, Double>> map = new HashMap<>();\n        \n        for(int i=0; i<edges.length; i++){\n            map.putIfAbsent(edges[i][0], new HashMap<>());\n            map.putIfAbsent(edges[i][1], new HashMap<>());\n            map.get(edges[i][0]).put(edges[i][1], succProb[i]);\n            map.get(edges[i][1]).put(edges[i][0], succProb[i]);\n        }\n        \n        Set<Integer> visited = new HashSet<>();\n        \n        PriorityQueue<double[]> queue = new PriorityQueue<double[]>((a, b) -> new Double(b[1]).compareTo(new Double(a[1])));\n        queue.add(new double[]{start, 1.0});\n        \n        while(!queue.isEmpty()) {\n            double[] cur = queue.poll();\n            \n            int curNode = (int)cur[0];\n            double curWeight = cur[1];\n            \n            if(curNode == end) {\n                return curWeight;\n            }\n            \n            if(!visited.contains(curNode)) {\n                visited.add(curNode);\n                \n                for(Map.Entry<Integer, Double> next: map.getOrDefault(curNode, new HashMap<>()).entrySet()) {\n                    int nKey = next.getKey();\n                    double nextWeight = next.getValue();\n                    \n                    queue.add(new double[]{nKey, curWeight * nextWeight});\n                }\n            }\n        }\n        return 0;\n    }\n}\n```\n\n**787. Cheapest Flights Within K Stops**\n\n```\n/*\nIt\'s same as Dijkstra algorithm to calculate distance btween two nodes when we have weights. I use BFS approach. \n\nFor Example:            4\n                    (1) |\n                        |   (4)\n                        0--------1               In this Example if my src is 0 and destination is 3 and K = 2\n                        |        |                     then the total cost of ticket is 4: (0->2->3)\n                    (2) |        | (5)\n                        |        |\n                        2--------3\n                            (2)\n\nStep 1: Create an adjacency list from given Matrix\n                0-> [(4,1) -> (1,4) -> (2,2)]\n                1-> [(3,5)]\n                2-> [(3,2)]\n                3-> [(1,5)]\n                4-> []\n\nStep 2: Sort Every int[] arr ({nextDestination, totalCostToReachThatDestination, K-1}) based on cost.\n        So Low cost will be at the starting of the PQ. It\'s min PQ\n\n\nStep 3: Get Node int[] from PQ and get it\'s sub next destination places and put back to the Queue to sort based on cost.Once u get destination return cost. \n*/\n\nclass Solution {\n    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {\n        Map<Integer, List<int[]>> map = new HashMap<>();\n        \n        //Step 1:\n        for(int[] flight : flights) {\n            map.putIfAbsent(flight[0], new ArrayList<>());\n            map.get(flight[0]).add(new int[]{flight[1], flight[2]});\n        }\n        \n        Map<Integer, Integer> visited = new HashMap<>(); // This is extra step to avoid TLE\n        \n        // Step 2:\n        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b) -> (a[1]-b[1]));\n        queue.add(new int[]{src, 0, k});\n        \n        \n        // Step 3:\n        while(!queue.isEmpty()) {\n            int[] cur = queue.poll();\n            \n            int curNode = cur[0];\n            int curPrice = cur[1];\n            int remainingStop = cur[2];\n            \n            if(curNode == dst) {\n                return curPrice;\n            }\n            \n            visited.put(curNode, remainingStop);   // To avoid TLE\n            \n            if(remainingStop >= 0 ) {\n                for(int[] temp : map.getOrDefault(curNode, new ArrayList<>())) { \n                    if(!visited.containsKey(temp[0]) || remainingStop > visited.get(temp[0]))  // This condition is to avoid TLE otherwise we add in PQ\n                    {\n                        queue.add(new int[]{temp[0], temp[1]+curPrice, remainingStop-1});\n                    }\n                }\n            }\n        }\n        return -1;\n    }\n}\n```\n\n**1584. Min Cost to Connect All Points**\n\n```\n// This problem is to create MST from so we use Prim\'s Algorithm. Prims Algo is almost similar to Dijkstra\'s Algo\n\nclass Solution {\n    public int minCostConnectPoints(int[][] points) {\n        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b) -> a[2] - b[2]);\n        queue.add(new int[]{0,0,0});\n        \n        Set<Integer> visited = new HashSet();\n        \n        int cost = 0;\n        int len = points.length;\n        \n        while(!queue.isEmpty() && visited.size()<len) {\n            int[] pq = queue.poll();\n            int curNode = pq[0];\n            int endNode = pq[1];\n            int curCost = pq[2];\n            \n            if(visited.contains(endNode)) {\n                continue;\n            }\n            cost = cost + curCost;\n            \n            visited.add(endNode);\n            \n            for(int i=0; i<len; i++) {\n                if(!visited.contains(i)) {\n                    queue.add(new int[]{endNode, i, distance(points, endNode, i)});\n                }\n            }\n        }\n        \n        return cost;\n        \n    }\n    \n    private int distance(int[][] points, int i, int j) {\n        return Math.abs(points[i][0]-points[j][0]) + Math.abs(points[i][1] - points[j][1]);\n    }\n}\n```\n\n**778. Swim in Rising Water**\n\n```\nclass Solution {\n    public int swimInWater(int[][] grid) {\n        int result = 0;\n        int m = grid.length;\n        int n = grid[0].length;\n\n        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a,b) -> a[0] - b[0]);\n        minHeap.add(new int[]{grid[0][0],0,0});\n\n        boolean[][] visited = new boolean[m][n];\n        visited[0][0] = true;\n\n        int[][] dirs = {{0,-1}, {0,1}, {1,0}, {-1,0}};\n\n        while(!minHeap.isEmpty()) {\n            int[] temp = minHeap.poll();\n\n            int curHeight = temp[0];\n            int curRow = temp[1];\n            int curCol = temp[2];\n\n            if(curRow == m-1 && curCol == n-1) {\n                return curHeight;\n            }\n\n            for(int[] dir : dirs) {\n                int x = curRow + dir[0];\n                int y = curCol + dir[1];\n\n                if(x>=0 && x<m && y>=0 && y<n && visited[x][y] == false) {\n                    visited[x][y] = true;\n                    minHeap.add(new int[]{Math.max(curHeight, grid[x][y]), x, y});\n                }\n            }\n        }\n\n        return -1;\n    }\n}\n\n```\n\n**1976. Number of Ways to Arrive at Destination**\n\n```\n/* \nThis Problem is same as Dijkstra\'s algortim. It\'s  \njust modulo(10^9 + 7) in the given input is making it slightly complex. stick to the same logic for the Dijsktra\'s algo \nand you will easily come up with the solution in the interview. \n*/\n\nclass Solution {\n    public int countPaths(int n, int[][] roads) {\n        Map<Integer, Map<Integer, Long>> map = new HashMap<>();\n\n        for(int i=0; i<roads.length; i++) {\n            map.putIfAbsent(roads[i][0], new HashMap<>());\n            map.putIfAbsent(roads[i][1], new HashMap<>());\n        \n            map.get(roads[i][0]).put(roads[i][1], (long)roads[i][2]);\n            map.get(roads[i][1]).put(roads[i][0], (long)roads[i][2]);\n        }\n\n        int[] ways = new int[n];\n        long[] distance = new long[n];\n        Arrays.fill(distance, Long.MAX_VALUE/2);\n        Arrays.fill(ways, 0);\n\n        ways[0] = 1;\n        distance[0] = 0;\n\n        int mod = (int)(1e9+7);\n\n        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a,b) -> a[0] - b[0]);\n        minHeap.add(new int[]{0,0,0});\n\n        while(!minHeap.isEmpty()) {\n            int[] temp = minHeap.poll();\n\n            long curDist = temp[0];\n            int curNode = temp[1];\n            int endNode = temp[2];\n\n            for(int next : map.getOrDefault(curNode, new HashMap<>()).keySet()) {\n                long nextDist = map.get(curNode).get(next);\n\n                if(curDist + nextDist < distance[next]) {\n                    distance[next] = curDist + nextDist;\n                    minHeap.add(new int[]{(int)(curDist + nextDist), next, endNode});\n                    ways[next] = ways[curNode];\n\n                } else if(curDist + nextDist == distance[next]) {\n                    ways[next] = (ways[next] + ways[curNode]) % mod; \n                }\n            }\n        }\n\n        return ways[n-1] % mod;\n    }\n}\n\n```\n\n**1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance**\n\n```\nclass Solution {\n    public int findTheCity(int n, int[][] edges, int distanceThreshold) {\n        int result = -1;\n        int minRechable = Integer.MAX_VALUE;\n\n        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();\n\n        for(int i=0; i<edges.length; i++) {\n            map.putIfAbsent(edges[i][0], new HashMap<>());\n            map.putIfAbsent(edges[i][1], new HashMap<>());\n\n            map.get(edges[i][0]).put(edges[i][1], edges[i][2]);\n            map.get(edges[i][1]).put(edges[i][0], edges[i][2]);\n        }\n\n        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a,b) -> a[0] - b[0]);\n\n        for(int i=0; i<n; i++) {\n            int[] distance = new int[n];\n            minHeap.add(new int[]{0,i});\n\n            Arrays.fill(distance, Integer.MAX_VALUE/2);\n            distance[i] = 0;\n            \n            while(!minHeap.isEmpty()) {\n                int[] temp = minHeap.poll();\n                \n                int curDist = temp[0];\n                int curNode = temp[1];\n\n                for(int next : map.getOrDefault(curNode, new HashMap<>()).keySet()) {\n                    int nextDist = map.get(curNode).get(next);\n\n                    if(curDist + nextDist < distance[next]) {\n                        distance[next] = curDist + nextDist;\n                        minHeap.add(new int[]{curDist + nextDist, next});\n                    }   \n                }\n            }\n            int rechable = 0;\n\n            for(int k=0; k<distance.length; k++) {\n                if(distance[k] <= distanceThreshold) {\n                    distance[k] = distanceThreshold;\n                    rechable++;\n                }\n            }\n\n            if(minRechable >= rechable) {\n                minRechable = rechable;\n                result = i;\n            }\n        }\n\n        return result;\n    }\n}\n```
['Java']