Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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



> 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)


Not 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.


IIRC you can express it with matrix multiplication, but there might be some big caveats on that.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: