"We are to prepare a proposal, a railway network proposal for the new government", bellowed the Head of the Logistic Department, a minute figure of a man.
Asha gazed at the map, a map of Bhutan, her team of engineers flanking her.
(copyright: http://www.bhutanyontentours.com/bhutan/47-2/)
As the chief engineer, she bore the the burden of leading the effort on the technical side. So the weight of Bellman's bellowing fell upon her. Bellman made neither a speech nor any further elaboration other than that the network needs to cover the 8 most major cities in Bhutan. He promised to come back the next morning to receive an update, a promise that was more like a threat than a promise to Asha and her team.
"So how do we do it?", grumbled Kavi, scratching his round beard. "Think of something", retorted Asha. She was drawing on a white board a layout of the cities listed by Bellman. No names, just numbers for each of the cities - from 0 to 7. Asha knew the places; in fact, she had been there, experienced the life there, as an expatriate engineer. But being a well-engineered engineer, she preferred numbers of course. Cities were dots on the drawing and an edge drawn between cities where Asha deemed a rail is feasible, given her knowledge of the terrain and distance. Numbers on the edges denoted distances in hundred of kilometers.
"We can't enumerate all possible rail networks, right?", Moses interjected. One of the senior engineers in the team, he was twiddling his pen like a kerambit as he studied Asha's drawing. "No, we can't", said Asha matter-of-factly, apparently unimpressed with the slight hint of algorithmic awareness in her team. She already knew there would be too many, a factorial number of possibilities if they were to work that way.
A solution started to shape in her head, clouded though it was as she gazed hard at the board. "What if we start here", she said, pointing to node 0. "It's not a path we are looking at, Asha", said Moses, "We don't have a starting point". Asha glared at him. "Yes, I know", she rebuked. "What I am saying is that .. what I want is to consider 0 as the only node in our network of road.", she said. She paraded her idea - assume that 0 to be the starting network of roads - a trivial start of course, one with only one city and no rail. Then progressively add the city closest to the network.
So we start from 0.
0 is the only city now in our minimal network of connected cities, M.
What's the nearest city to the network?
It's 1, right?
What's next?
Now, note that we have 2 cities now in our network, M.
So the next nearest may be nearest with respect to its distance to either 0 or 1.
That's going to be 7, right?
Let's go on.
What's nearest to the network now?
3, right?
Now, 2.
As you can see here.
Then 5.
Are you getting it?
And so on and so forth.
Asha completed her network, an air of triumph about her, an air of awe enveloping everyone else. None others, except for maybe Moses, understood really how it could work, but it did work. Nothing else they can offer could beat the network derived by Asha in terms of distance.
"That's a good one, Asha", said Kavi, still rubbing his beard. "What shall we call it, this network?"
"Minimum Spanning Tree", quipped Asha. "The algorithm?", asked someone else. "Shall it have a name?"
Prim's Algorithm.
The Python code
# assume
#cities = a list of points
#graph = the adjacency matrix
#vertices = number of cities
# initialize the MST and the set X
T = {}
X = {}
# select an arbitrary vertex to begin with
X.add(0)
while len(X) != vertices:
crossing = set() # a set object
# for each element x in X, add the edge (x, k) to crossing if
# k is not in X
for x in X:
for k in range(vertices):
if k not in X and graph[x][k] > 0:
crossing.add((x, k)) # the possible edges
# find the edge with the smallest weight in crossing
edge = sorted(crossing, key=lambda e:graph[e[0]][e[1]])[0]
# add this edge to T
T.add(edge)
# add the new vertex to X
X.add(edge[1])
# print the edges of the MST
for edge in T:
print(edge)
No comments:
Post a Comment