Years ago I looked into treating pathfinding in EVE as a graph problem because I was annoyed by losing money in the collapse of the Mt. Gox scam and read that its owner had solved the same problem. I thought I'd show him up by showing how easy it is to blow his terrible PHP code out of the water. :)
You can find the writeup and a link to the code on my blog:
Just a note, unless you have negative edges, running V Dijkstra's is likely to perform better than Floyd Warshall. Dijkstra's gives you distance from a single node to all other nodes in V log E time. If you run it V times, you'll get V^2 log E, a substantial improvement upon V^3.
It also seems to me like it's likely to be easier parallelized, considering that the V runs of Dijkstra are completely independent.
Hmm, wouldn't Dijkstra's be V E + V^2 log V? I take your point though. I suspect that I was dazzled by the cache locality advantages of dynamic programming and skeptical that messing about with a bunch of heap nodes would be faster, but looking at it now I bet you're right that knocking one of those Vs down to a log V would help. Thanks for the feedback!
You can find the writeup and a link to the code on my blog:
https://briangordon.github.io/2014/03/better-pathfinding.htm...