Skip to content

Instantly share code, notes, and snippets.

@alieseparker
Last active January 1, 2018 14:26
Show Gist options
  • Save alieseparker/767eae60c9bc83decfd4 to your computer and use it in GitHub Desktop.
Save alieseparker/767eae60c9bc83decfd4 to your computer and use it in GitHub Desktop.
Floyd-Warshall - Find shortest path
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment