2 ms·
I know LLMs are all the rage, but I’m genuinely shocked at the new fastest path algo for negative weight graphs. That’s awesome!
by elijahbenizzy 3y ago
I know LLMs are all the rage, but I’m genuinely shocked at the new fastest path algo for negative weight graphs. That’s awesome!
- ckcheng 3y agoRelevant Quanta article: https://www.quantamagazine.org/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118/ https://www.quantamagazine.org/finally-a-fast-algorithm-for-... The CACM article discussed here at the time (just 3 months ago!): https://news.ycombinator.com/item?id=37275676 https://news.ycombinator.com/item?id=37275676 The relevant paper is https://arxiv.org/abs/2203.03456 https://arxiv.org/abs/2203.03456 and an improvement here https://arxiv.org/abs/2304.05279 https://arxiv.org/abs/2304.05279 I wonder if this will become standard curriculum for undergrads sooner rather than later. It's apparently a very simple and approachable method.
- elijahbenizzy 3y agoWonderful! Yeah, admittedly, I haven't sat out and drawn it out (my process for learning algorithms is often just do it by hand until it intuitively makes sense), but it did strike me as pretty straightforward on first glance. Thanks!