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