Programming Problems #3 : Muddy City Problem

Solving the muddy city problem using a graph algorithm

Today, we will discuss a famous graph problem known as the muddy city problem. We will implement the solution to this problem in Python using the concept of a Minimum Spanning Tree (MST).

Problem Statement

“Once upon a time, there was a city that has no roads. Getting around the city was particularly difficult after rainstorms because the ground becomes very muddy cars, got stuck in the mud and people got their boots dirty. The mayor wants to revamp the city, but he didn’t want to spend more money than necessary because it also wanted to build other things. Mayer, therefore, specified two conditions:

1. Enough streets must be paved so that everyone can travel from their house to anyone else home only along paved roads, and
2. The paving should cost as little as possible.”

The Muddy City Problem

The problem statement tells us two things

1. We need a set of pavements to connect every house in the city
2. Cost should be minimum

For those already familiar with graph theory, the most obvious guess would be to construct a Minimum Spanning Tree (MST). The input to the program would be an adjacency matrix as shown below :

adjacency_matrix = [[0, 2, 0, 6, 0],
                    [2, 0, 3, 8, 5],
                    [0, 3, 0, 0, 7],
                    [6, 8, 0, 0, 9],
                    [0, 5, 7, 9, 0]]

and the output would be an MST of the form (start, end : edge weights).

0 1 : 2
1 2 : 3
1 4 : 5
0 3 : 6

What is a Minimum Spanning Tree ?

If you consider the houses in the city to be nodes of a graph, the MST would be a path/tree that spans each and every node of the graph with an overall minimum cost. There are multiple algorithms used to find the MST. We will be using Prim’s algorithm to solve this problem. If you are interested in studying MST algorithms in greater detail refer to this link.

Prim’s Algorithm

Prim’s algorithm is a greedy algorithm for finding Minimum Spanning Trees in a graph. It does so by adding vertices to the growing spanning tree, choosing the vertex with the minimum weighted edge at each step. The steps of the algorithm are as follows:

1. Maintain a list of visited vertices in the MST.
2. Set the minimum distance as infinity to each node. Select a random starting vertex.
3. Choose the edge with minimum weight connected to the chosen vertex by looping through the neighboring vertices.
4. Set the vertex as visited. Update the minimum distance to the minimum distance from chosen vertex to a neighbor.
5. Repeat steps 3&4 until all the vertices have been visited.

If you have scoured the internet for resources on Prim’s algorithm like me, you may have seen versions of the algorithm on with different steps and complexities. I understand this is quite confusing, so let me break it down for you.

The complexity of the algorithm above is O(V³) due to the presence of 3 nested loops. This is rather inefficient. Luckily, a simple trick can make reduce the complexity to O(V²). We will use a function to find the minimum cost edge for every vertex without including it in the main loop every time. The program will look something like this :

If we were using an adjacency list instead of a matrix, the complexity can be reduced by using a priority queue to maintain adjacent vertices in order of their edge- weights. In the textbook “ Introduction to algorithms”, Prim’s algorithms is implemented with the priority queue. The complexity of the algorithm in that case is O((V+E)logV).

References

1. https://edward-huang.com/graph-theory/algorithm/2021/01/21/solving-the-muddy-city-problem-with-minimum-spanning-tree/
2. https://stackabuse.com/graphs-in-python-minimum-spanning-trees-prims-algorithm/
3. https://kalkicode.com/prims-algorithm-using-adjacency-matrix
4. https://www.algotree.org/algorithms/minimum_spanning_tree/prims_python/
5. https://www.cs.cmu.edu/afs/cs/academic/class/15451-s04/www/Lectures/minimumSpanningTrees.pdf