Put your message here! Contact me for more information
 

 







 

Floyd-Warshall’s Shortest Path

I was studying for a CS417 exam and found the Floyd-Warshall’s algorithm very interesting. It uses an adjacency matrix to define a weighted, directed graph. It uses dynamic programming so it’s fairly efficient and fast with a complexity of O(n^2). The recurrence relation is surprisingly simple but works well in this case. Yay to Dynamic Programming!
Here is a quick Floyd’s algorithm implementation in Javascript. Currently the scripts only works with Firefox because I focused more on the functionalities but not compability.

If you’d like to use the code immediately in your applications, just rewrite the floyd() method to accept a 2D array containing the weighed edges, then remove those code for HTML. The algorithm should take care of the rest and give you back a nicely shortest-path graph (in 2D array representation).
Lastly, the source code is free for public uses (no copyright but again, no guarantee of any sorts from me!). Any comments/ suggestion please send to me at nworld3d@yahoo.com.