Floyd-Warshall - Find shortest path

Floyd-Warshall

# Floyd-Warshall Algorithm
## Introduction:
Finds Shortest Path (or longest path) among all pairs of nodes in a graph.
Complexity: O(|n|³)


## How does it work?
- There can be more than one route between two nodes.
- The number of nodes in the route isn’t important (Path 4 has 4 nodes but is shorter than Path 2, which has 3 nodes)
- There can be more than one path of minimal length
Check out this pic for an example!
https://www.dropbox.com/s/9a9zq55bbs2rsig/floyd-warshall-example.jpeg?dl=0


## Ok, lets break it down
 We start by building an adjacency graph that measarues the distance between each node
 it'll look something like this.
 
 	  House	  Park	  Mall	  Gym	F-ball	   Pizza
  House	    0      8	   2	   4	   5	     4
  Park	    8	   0	   x	   x	   x	     x
  Mall	    2	   5	   0	   1	   x	     x
  Gym	    4	   x	   x	   0	   1	     x
  F-ball    5	   x	   x	   1	   0	     0
  Pizza	    4	   x	   x	   x	   x	     0
  
Next we want to build a graph through another point, and if the distance is less than
the value in our current graph.  In this example we will run through the mall.

Through the mall.
 	  House	Park	Mall	Gym	F-ball	Pizza
  House	    0    7	 2	 3	   x	  x
  
Which if you notice by using the mall the distance between the house and park is one less, same with the
distance between the house and gym.  Thus, we would continue through each of these nodes through
another node and update the list everytime we find a shorter path.


## Here's some psuedo code
```Ruby
for i = 1 to N
   for j = 1 to N
      if there is an edge from i to j
         dist[0][i][j] = the length of the edge from i to j
      else
         dist[0][i][j] = INFINITY
  
for k = 1 to N
   for i = 1 to N
      for j = 1 to N
         dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])
```
Remember, it’s just code.

i = Starting Point
j = Ending Point
k = intermediate Point


## Contributions
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
http://ezetter.blogspot.com/2009/04/warshalls-algorithm-in-ruby.html
http://www.quora.com/What-is-an-intuitive-explanation-of-the-Floyd-Warshall-algorithm