"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?
No comments:
Post a Comment