30 Sep Application of different algorithms
Let’s say you have a network with many PC connected in following way.
Here, each node represents a PC and the number on each link represents the cost needed to maintain those links.
Our job is to minimize the cost and still have a path from a node to any other given node.
A good way to solve this is to be “Greedy”.
One of the greedy algorithms to solve this problem of finding the Minimum Spanning Tree is the Kruskal’s algorithm.
According to this algorithm, In each iteration, select the least cost path such that the selection won’t create a cycle. A tree, as you know, cannot have any cycle. There exists a unique path between any 2 given nodes.
So, according to this algorithm, if you keep selecting the least cost path in each iteration you will end up making the following selections.
Note in step 6 that even though the next least link was the link at bottom labelled 6, we didn’t select it because it would create a cycle.
The algorithm terminates when we find N-1 edges where N is the number of nodes.
Hence, the minimum spanning tree is
Using a greedy algorithm, you have minimized the cost to lay the network and still maintain connectivity between every PC.
Most Popular Friend
There is another problem that I came across in a programming contest.
According to this problem:- We are planning an event, and we want as many people as possible to attend the event.
One way to spread the event information is to post it on wall of face book profiles. But we don’t want to spam everyone’s wall with posts. So, we decide to find out the most popular friend in a group and post it on his/her wall so that he can spread the information to others.
Here, a popular friend is defined as a person whose distance to all others is least. Distance of person X to person Y is the number of profiles you have to hop to reach Y.
We represent this information in a format known as adjacency matrix.
Here, A is friend of B, C, D.
B is friend of A, D.
C is friend of A, D, E.
D is friend of A, C, B, F.
E is friend of C.
F is friend of D.
Hence, for ex- distance of A from E is 2, and distance of F from E is 3.
Our task is to compute the shortest distance from each node to every other node.
There exists a Dynamic programming algorithm to do this. It is called Floyd’s algorithm.
Assume that we represent the graph as a matrix.
Here, INFINITE means that there is no direct path between the corresponding nodes labelled with row-column, and 1 means there is a direct path between those nodes.
So, what is the principle behind Floyd’s algorithm?
Consider a set of nodes in a graph labelled 1 to N. Assume that we have to find shortest path from node X to node Y using only nodes 1 to K as intermediate nodes.
There exist 2 possible candidates for this solution.
1) A path that goes from i to j using only the nodes 1 to K as inter mediatory nodes, as assumed above.
2) A path that goes from 1 to K+1 and then goes from K+1 to the destination.
Our solution is the one whichever is shortest.
So, our recurrence relation is
Path ( X , Y , K ) = minimum ( Path ( X , Y , K-1) , Path ( X , K , K-1)+Path ( K , Y , K-1) )
If you notice carefully, we are computing something again and again.
We are defining length from node X to node Y using K intermediate nodes in terms of length from X to Y using K-1 intermediate nodes or X to K+1 , K+1 to J , whichever is shortest .
Instead of computing these things again and again in each step, we can compute the values in a Bottom-up fasion and store it in advance and retrieve it in later stages and use it for our calculation.
Converting this into a Dynamic programming approach. The algorithm is as follows:-
Algorithm to calculate shortest path from every node to every other node
Input: An adjacency matrix defining the distance between the nodes.
Output: An adjacency graph indication shortest path from each node to every other node.
For K=1 to N
For I=1 to N
For J=1 to N
friend [I] [J] = min ( friend [I] [J] , friend [I] [K] + friend [K] [J] )
This algorithm has time complexity of Ө(N^3) and after N^3 passes, the array friend contains the shortest path from each node to every other node.
After running this on above example, we will get following result.
Now, we know the distance from each person to every other person. So all we have to do is, find the sum for all people and find the least.
A = 0 + 1 + 1 + 1 + 2 + 2 = 7
B = 1 + 0 + 2 + 1 + 3 + 2 = 9
C = 1 + 2 + 0 + 1 + 1 + 2 = 7
D = 1 + 1 + 1 + 0 + 2 + 1 = 6
E = 2 + 3 + 1 + 2 + 0 + 3 =11
F = 2 + 2 + 2 + 1 + 3 + 0 = 10
D is closest to all with total distance 6. Hence, D is the most popular friend of the group.
Hence, it is enough if we post our invitation on D’s wall.
This article has been written by Manohar Prabhu.