3 ms·
It would be hard to beat Floyd–Warshall algorithm. Think about the problem of finding shortest paths between all pairs of nodes in graph. Sounds trivial? Would
by sytelus 8y ago
It would be hard to beat Floyd–Warshall algorithm. Think about the problem of finding shortest paths between all pairs of nodes in graph. Sounds trivial? Would you believe if someone told you it can be done in literally 5 lines of code? When I saw that for the first time I was in the disbelief. The elegance comes from these fact,
- Very non-trivial problem
- Just 5 lines of code
- Probably the most language agnostic algorithm
- Outrageously fast if graph fits in cache
- You can explain it to even non-programmers
- You can wear it on T-Shirt
- Doesn't require any fancy sub-algorithms, libraries or whatever
- 0-_-0 8y ago> Probably the most language agnostic algorithm Are you sure about this point? I'd like to see a purely functional implementation of this, e.g. in Haskell without monoids. I believe it's significantly harder than a C implementation (which is indeed a few lines)
- jaspervdj 8y agoNot really, if you wanted to do a version using only immutable arrays: import Data.Array fw :: Int -> Array (Int, Int) Int -> Array (Int, Int) Int fw 0 graph0 = graph0 fw k graph0 = let fw' = fw (k - 1) graph0 in array (bounds graph0) [ ((i, j), min (fw' ! (i, j)) ((fw' ! (i, k)) + (fw' ! (k, j)))) | (i, j) <- range (bounds graph0) ] The only difference with a mutable implementation is that you use a new array for every k, whereas in a mutable version you would reuse these.
- andrewflnr 8y agoIIRC you can express it with matrix multiplication, but there might be some big caveats on that.