[curiousgibbon]

Negative weight single source shortest paths in near-linear time: https://arxiv.org/abs/2203.03456

Obligatory Quanta link: https://www.quantamagazine.org/finally-a-fast-algorithm-for-...

[nodespace]

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