min_cost_to_connect_all_points
1from heapq import heappop, heappush 2 3 4# @leet start 5def manhattan_distance(p1: list[int], p2: list[int]) -> int: 6 return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1]) 7 8 9class Solution: 10 def minCostConnectPoints(self, points: list[list[int]]) -> int: 11 """ 12 This question asks us the minimum cost to connect all points 13 in a given graph, with the distasnce being the manhattan distance. 14 So, this is a Minimum Spanning Tree (MST) problem. 15 16 We can use Prim's algorithm for this, which uses a heap to greedily 17 find the lowest-weighted edge that connects a node outside of the MST 18 to one that's in the MST. 19 As well, since an MST can only have $n - 1$ edges, once we've iterated 20 that many times, we can break out of the loop. 21 22 So the algorithm is as follows: 23 1. Create a min-heap with the starting node, 0, and a cost of 0. 24 2. For each point, we want to find the minimum 25 distance that this point has to connect to all the other points 26 if we choose this current point. 27 2a. If we've already visited this point's neighbors, ignore it. 28 2b. If the total distance to this node's neighbors is larger than 29 the current distance, ignore it. 30 2c. Otherwise, we've found a new shortest path to the node. We update 31 our distance and check if any shorter distances exist. 32 33 Finally, after $n$ iterations, we exit. This algorithm takes $O(n^2) * log\{n}$ time 34 and O(n^2)$ space. 35 """ 36 n = len(points) 37 visited = set() 38 heap_dict = {0: 0} 39 min_heap = [(0, 0)] 40 41 mst_weight = 0 42 43 while min_heap: 44 w, u = heappop(min_heap) 45 46 if u in visited or heap_dict.get(u, float("inf")) < w: 47 continue 48 49 visited.add(u) 50 mst_weight += w 51 52 for v in range(n): 53 if v not in visited: 54 new_distance = manhattan_distance(points[u], points[v]) 55 56 if new_distance < heap_dict.get(v, float("inf")): 57 heap_dict[v] = new_distance 58 heappush(min_heap, (new_distance, v)) 59 60 return mst_weight
def
manhattan_distance(p1: list[int], p2: list[int]) -> int:
class
Solution:
10class Solution: 11 def minCostConnectPoints(self, points: list[list[int]]) -> int: 12 """ 13 This question asks us the minimum cost to connect all points 14 in a given graph, with the distasnce being the manhattan distance. 15 So, this is a Minimum Spanning Tree (MST) problem. 16 17 We can use Prim's algorithm for this, which uses a heap to greedily 18 find the lowest-weighted edge that connects a node outside of the MST 19 to one that's in the MST. 20 As well, since an MST can only have $n - 1$ edges, once we've iterated 21 that many times, we can break out of the loop. 22 23 So the algorithm is as follows: 24 1. Create a min-heap with the starting node, 0, and a cost of 0. 25 2. For each point, we want to find the minimum 26 distance that this point has to connect to all the other points 27 if we choose this current point. 28 2a. If we've already visited this point's neighbors, ignore it. 29 2b. If the total distance to this node's neighbors is larger than 30 the current distance, ignore it. 31 2c. Otherwise, we've found a new shortest path to the node. We update 32 our distance and check if any shorter distances exist. 33 34 Finally, after $n$ iterations, we exit. This algorithm takes $O(n^2) * log\{n}$ time 35 and O(n^2)$ space. 36 """ 37 n = len(points) 38 visited = set() 39 heap_dict = {0: 0} 40 min_heap = [(0, 0)] 41 42 mst_weight = 0 43 44 while min_heap: 45 w, u = heappop(min_heap) 46 47 if u in visited or heap_dict.get(u, float("inf")) < w: 48 continue 49 50 visited.add(u) 51 mst_weight += w 52 53 for v in range(n): 54 if v not in visited: 55 new_distance = manhattan_distance(points[u], points[v]) 56 57 if new_distance < heap_dict.get(v, float("inf")): 58 heap_dict[v] = new_distance 59 heappush(min_heap, (new_distance, v)) 60 61 return mst_weight
def
minCostConnectPoints(self, points: list[list[int]]) -> int:
11 def minCostConnectPoints(self, points: list[list[int]]) -> int: 12 """ 13 This question asks us the minimum cost to connect all points 14 in a given graph, with the distasnce being the manhattan distance. 15 So, this is a Minimum Spanning Tree (MST) problem. 16 17 We can use Prim's algorithm for this, which uses a heap to greedily 18 find the lowest-weighted edge that connects a node outside of the MST 19 to one that's in the MST. 20 As well, since an MST can only have $n - 1$ edges, once we've iterated 21 that many times, we can break out of the loop. 22 23 So the algorithm is as follows: 24 1. Create a min-heap with the starting node, 0, and a cost of 0. 25 2. For each point, we want to find the minimum 26 distance that this point has to connect to all the other points 27 if we choose this current point. 28 2a. If we've already visited this point's neighbors, ignore it. 29 2b. If the total distance to this node's neighbors is larger than 30 the current distance, ignore it. 31 2c. Otherwise, we've found a new shortest path to the node. We update 32 our distance and check if any shorter distances exist. 33 34 Finally, after $n$ iterations, we exit. This algorithm takes $O(n^2) * log\{n}$ time 35 and O(n^2)$ space. 36 """ 37 n = len(points) 38 visited = set() 39 heap_dict = {0: 0} 40 min_heap = [(0, 0)] 41 42 mst_weight = 0 43 44 while min_heap: 45 w, u = heappop(min_heap) 46 47 if u in visited or heap_dict.get(u, float("inf")) < w: 48 continue 49 50 visited.add(u) 51 mst_weight += w 52 53 for v in range(n): 54 if v not in visited: 55 new_distance = manhattan_distance(points[u], points[v]) 56 57 if new_distance < heap_dict.get(v, float("inf")): 58 heap_dict[v] = new_distance 59 heappush(min_heap, (new_distance, v)) 60 61 return mst_weight
This question asks us the minimum cost to connect all points in a given graph, with the distasnce being the manhattan distance. So, this is a Minimum Spanning Tree (MST) problem.
We can use Prim's algorithm for this, which uses a heap to greedily find the lowest-weighted edge that connects a node outside of the MST to one that's in the MST. As well, since an MST can only have $n - 1$ edges, once we've iterated that many times, we can break out of the loop.
So the algorithm is as follows:
- Create a min-heap with the starting node, 0, and a cost of 0.
- For each point, we want to find the minimum distance that this point has to connect to all the other points if we choose this current point. 2a. If we've already visited this point's neighbors, ignore it. 2b. If the total distance to this node's neighbors is larger than the current distance, ignore it. 2c. Otherwise, we've found a new shortest path to the node. We update our distance and check if any shorter distances exist.
Finally, after $n$ iterations, we exit. This algorithm takes $O(n^2) * log{n}$ time and O(n^2)$ space.