Finally, a Fast Algorithm for Shortest Paths on Negative Graphs(quantamagazine.org)
quantamagazine.org
Finally, a Fast Algorithm for Shortest Paths on Negative Graphs
https://www.quantamagazine.org/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118/
6 コメント
Whoa, this is huge! I love the explanation too. The low-diameter decomposition part was very interesting. This is one of the things I love about graph theory- there are so many solved and nearly-solved problems and concepts that might be useful to each other. It's like a problem set that comes with its own toolbox to tinker with.
Does this give any insight into the Traveling Salesman problem? The salesman would with some probability make some bigger sales on some cities while less so in other cities.
I think this gives a good more realistic viewpoint on all these graph-traversal problems. Of course the only reason to traverse any graph in some way would be if there is some benefit meaning negative cost for traversing it.
I think this gives a good more realistic viewpoint on all these graph-traversal problems. Of course the only reason to traverse any graph in some way would be if there is some benefit meaning negative cost for traversing it.
Anyone have the paper link or a pseudocode of the actual algorithm? I assume it's somewhere in the article, but I swear I can't find it.
Thanks. Yeah that's not too terribly complicated.
I was expecting something simpler tbh, but it still looks like a decent undergrad could implement it without too much trouble, even without a supplementary writeup.
I was expecting something simpler tbh, but it still looks like a decent undergrad could implement it without too much trouble, even without a supplementary writeup.
Definitely worth looking at, the Bellman-Ford algorithm can traverse negative edges but is slower than Dijkstra's.
An interesting read!
An interesting read!