The algorithm says following.

At any stage all the vertices in the graph will be in one of the three states, temporary, permanent or undefined.

Initially all the vertices will be undefined.

1) Take a source vertex, make it’s permanent cost 0 and make it permanent.

At this stage we have one permanent vertex with zero cost and all other vertices are undefined.

2) For the vertices adjacent to the vertex you just made permanent, do following.

3) Calculate temporary cost which is equal to permanent cost of the vertex which you just made permanent + weight of edge between the last permanent vertex and current temporary vertex. If this new temporary cost is less than previous temporary cost of the vertex, replace it with new cost.

4) Repeat step 4 for all the vertices adjacent to the last permanent vertex.

5) select a temporary vertex with lowest temporary cost…

View original post 82 more words