4 ms·
Negative weight single source shortest paths in near-linear time: https://arxiv.org/abs/2203.03456 https://arxiv.org/abs/2203.03456 Obligatory Quanta link: htt
by curiousgibbon 3y ago
Negative weight single source shortest paths in near-linear time: https://arxiv.org/abs/2203.03456 https://arxiv.org/abs/2203.03456
Obligatory Quanta link: https://www.quantamagazine.org/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118/ https://www.quantamagazine.org/finally-a-fast-algorithm-for-...
- nodespace 3y agoAre there any implimentations of this? I got started working on one for rust, but got kinda stuck in a few places. This could be very useful for RTS AI I think, or anything where you need to optimize managing resources and build orders, if I understand negative weight shortest paths correctly.