Finally, a Fast Algorithm for Shortest Paths on Negative Graphs

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.

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.

Definitely worth looking at, the Bellman-Ford algorithm can traverse negative edges but is slower than Dijkstra's.

An interesting read!