Connecting Cities With Minimum Cost

Patrick Leaton

Published: Oct. 7, 2021, 8:15 p.m.

Problem Description

There are n cities labeled from 1 to n. You are given the integer n and an array connections where connections[i] = [xi, yi, costi] indicates that the cost of connecting city xi and city yi (bidirectional connection) is costi.

Return the minimum cost to connect all the n cities such that there is at least one path between each pair of cities. If it is impossible to connect all the n cities, return -1,

The cost is the sum of the connections' costs used.

Example 1:

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.

Example 2:

Input: n = 4, connections = [[1,2,3],[3,4,4]]
Output: -1
Explanation: There is no way to connect all cities even if all edges are used.

Constraints:

1 <= n <= 10^4
1 <= connections.length <= 10^4
connections[i].length == 3
1 <= xi, yi <= n
xi != yi
0 <= costi <= 10^5

The description was taken from https://leetcode.com/problems/connecting-cities-with-minimum-cost/.

Problem Solution

#O(E(Log(V))) Time, O(E+V) Space

class Solution:

    def minimumCost(self, n: int, connections: List[List[int]]) -> int:

        adjacency, seen = {}, {}

        output = 0

        

        for node in range(1, n+1):

            adjacency[node] = []

        

        for source, dest, cost in connections:

            adjacency[source].append((cost, dest))

            adjacency[dest].append((cost, source))

                

        heap = [(0,1)]

        while heap:

            cost, node = heapq.heappop(heap)

            if node in seen:

                continue

            seen[node] = True

            output += cost

            for path_cost, neighbor in adjacency[node]:

                if neighbor not in seen:

                    heapq.heappush(heap, (path_cost, neighbor))

        

        if len(seen) < n:

            return -1

        return output

Problem Explanation

This problem is very similar to Minimum Cost to Connect all Points. We are given an undirected weighted graph and are asked for the minimum cost to connect all of the points.

This type of problem belongs in the category of Minimum Spanning Trees.

There are many ways to solve these, but maybe one of the more intuitive solutions is Prim's algorithm, a variation of Dijkstra's which we can use to find the minimum cost to connect the shortest paths of each node by traversing each shortest path.

Let's start by initializing our adjacency list which we will use to map each node to its neighbors, and our dictionary for nodes that we have seen.

adjacency, seen = {}, {}

We will also need a counter that we'll output which we will increment by the weights of the shortest paths we travel.

output = 0

Let's go ahead and step through the list of nodes and initialize an empty list for each node that we will fill with its neighbors in a moment.

for node in range(1, n+1): adjacency[node] = []

For each connection from a node to its neighbor, we'll push the cost and the neighbor into the node's adjacency list. We will also need to do the same for the neighbor's list since these are undirected edges.

for source, dest, cost in connections: adjacency[source].append((cost, dest)) adjacency[dest].append((cost, source))

Next, we will begin our shortest path traversal starting from the first node.

We will initialize a heap with a tuple of zero and one. Since we are choosing node one as the source node, it will have an initial cost of zero to travel to it.

heap = [(0,1)]

While we have nodes in the heap, we will continue traveling the shortest paths.

while heap:

Each iteration will begin by popping the current shortest path between any two nodes from the heap and if we have seen the destination node before, we will skip it so that we don't revisit it.

If we have already seen it before, that means we have also seen a shorter path to it already.

cost, node = heapq.heappop(heap) if node in seen: continue

If not, we will mark it as seen, increment the output by the cost to get to it so that we are essentially traveling the path, and if we have not seen its neighbors, we will push them into the heap next with the cost to travel the path to them.

seen[node] = True output += cost for path_cost, neighbor in adjacency[node]: if neighbor not in seen: heapq.heappush(heap, (path_cost, neighbor))

If the length of nodes we have seen is less than the number of nodes we have, then that means there wasn't a path to some of the nodes so we will return a negative one.

Otherwise, we will return the cost to travel each shortest path.

if len(seen) < n: return -1 return output