__Introduction__

This is one of the most common algorithms that is used to get the shortest path from a single source point. This is useful since we can get the shortest distance to all the other points reachable from a single source point.

Lets see how this algorithm works,

let us start from the node 0

to 1 = 1

to 2 = 6

to 0 = 0

since we already covered 0 we no more consider it in our algorithm

so now we have updated the node 2

continuing the same the final result,

to 0 = 0 covered

to 1 = 1 covered

to 2 = 5

to 3 = 4

to 4 = 2

First we initiate all the nodes to distance infinity while having the starting node at distance 0, which is obvious.

from 0 we start traversal. Now we update the distances to the nearest node. Now distances are as follows

to 1 = 1

to 2 = 6

to 0 = 0

since we already covered 0 we no more consider it in our algorithm

For the shortest path to any node we should have the shortest path to every other node. So what we have to do is continue the previously done procedure ahead. Now take the node with the minimum distance node, which is 1 which has a distance 1 from 0. Update its neighbours now. The once that are not covered. Now

to 2 = 1(distance to 1) + 4 (distance 1 to 2) = 5so now we have updated the node 2

continuing the same the final result,

to 0 = 0 covered

to 1 = 1 covered

to 2 = 5

to 3 = 4

to 4 = 2

Now we continue the procedure for node 4 and update node 3 to be distance 3 (2 + 1). This continues with the remaining node 3 and 2 but the results don't change here since we already have the optima. This is a dynamic programming approach, thus the results does not hold always true. This algorithm fails for negative edges. Because it'll keep one jumping between two nodes without ending or giving an erroneous output.

__Program Code__

This can be easily implemented in java as follows

## No comments:

## Post a Comment