Bellman Ford Shortest Path Algorithm

"How to I get from A to other locations?", the Old Man pondered as he fingered the edges in the graph..

He took out his pen, a gift that's still alive from his long-dead spouse, and with a shaking hand, note down the list of roads, or paths or edges, in the graph, with number in brackets denoting the distance of a particular edge.

Those roads - they formed his walking paths, his daily morning routine. He would go to different sites each day from A his home: B a fountain in town, C his favorite restaurant, D the library, E his doctor. And F, his favorite spot in the town's botanical garden. He could not go too far, could not afford a route longer than it should be, as age had shown its effect, imparting laziness and a lesser resolve in him. He would like, not that he really needed, to know the distances from A to each of the other sites. For convenient record keeping, he drew out the following table, the entries for which would be the min distances.

At this time, sleepiness bore upon him. He could not go further. All he knew at the moment is that the distance from A to A is 0; for the rest, he assumed for a start a distance of infinity:

Sleep.

zzzz...

Awake.

Back to his table.

He looked at the list of edges: AB (6), BC(6) and so on...

He starts with AB(6).

The length of AB is 6, and the distance up to A, as noted in the table is 0.

It means that the distance up to B via A is 0 + 6 = 6.

Old Man smiled, gleefully showing the gaps in his teeth, as he updated his table.

On to the next edge, BC (6).

The distance at B is 6, and the distance from B to C is 6.

That added up to 12.

Another update to the table.

Old Man processed the next edge AF (5) in the same way.

He made further update to the table.

Now on to FB (5).

Distance up to F is 5, and the length of FB is 5.

It means that the distance to B via F is 5 + 5 equals to 10, right?

The Old Man wrinkled his wrinkles.

His mind blurry, as he tried to remember his thoughts.

He paused for a toilet break.

And he remembered he had yet to take his breakfast.

And while doing his business in the toilet, he remembered what he was trying to remember.

And it occurred to him.

He rushed out, oblivious to his nakedness and the open window.

If the distance to B via F is 10, and the distance at B is currently indicated as 6 in the table, then of course... of course, it means that there is no need for any update to the table.

The value currently stored in the table is better than the new one.

And so he maintained his table.

FB (5) left no mark on the table.

A different story with FC (6).

The distance up to F is 5, and the distance of FC is 6.

That totals up to 11, which is better than the 12 current indicated for C.

Old Man updated the table for C.

Another update in the table, this time for D.

From infinity to 12.

No go for DC (9).

It doesn't change anything.

Late morning, Old Man was done with all the edges.

He's hungry, but he wandered if he needed to repeat the steps.

Looking at the graph, eyeballing the distance, he noted that his outcome was indeed correct.

Still..

After lunch, he settled in to another possibility.

What if, he pondered, he got something like as follows:

He considered the list of edges to be as per the following order:

After considering all the edges, as per the sequence above, he obtained the following values in his table:

He needed to repeat.

Repeat he did, obtaining the following:

Another round, and he obtained the following:

Doing it again and again, for a total number of iterations of 5, he finally obtained the solution:

It seemed to him that a total of N-1 iterations is needed for his calculation approach to work, N being the number of nodes or sites.

Late evening, and he's yet to start his walk.

He's still thinking.

What if there are negative numbers on his edges?

Negative edges?

Negative numbers you mean? He thought, chuckling as he imagine what his wife would have said were she still to be alive.

But if the numbers were to represent some kind of points or merits or toll charges on the road, it would be realistic.

It's late in the evening. He has to retire.

He will sleep on his problems, now problems far removed from his original intent of simply calculating his walking distances.

Will his approach work for a graph with negative weights?

What if there is a cycle with negative total weights in the graph?

Can his approach deals with such?

Minimum Spanning Tree - Prim's Algorithm

"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)