Graph – Dijkstra’s algorithm to find shortest path.

Thought Page

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

Advertisements
Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s