Floyd Warshall – All Pair Shortest Path

Jaani Solves

Hi Readers,

Imagine yourself moving in a vehicle and suddenly you find a spot where your road diverges to many different roads. This is where you have to take a strategic decision, “Which road should I take?”. You can get an answer to this question in three ways:

  1. If you have already travelled to your destination, you would know which route to take (funny right?)
  2. If you have not travelled, you can refer your on-board GPS tracker(Global Positioning System) or ask someone for the route and proceed.
  3. If you have not travelled, you can take a wild guess based on some parameters (like distance to some intermediate location) and proceed.

The second and third case above are our areas of interest here.

The Third method is called “Greedy Algorithm“. Here, you don’t have to know the complete information to make your decision. You just take a greedy decision…

View original post 442 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