[sam2426679]

> Couldn’t you just preprocess the edges and normalize their weights?

In case it’s unclear, the article from OP is effectively doing this:

> The team found it was possible to divide the input graph into clusters of low-diameter subgraphs, and then to progressively rework the weights using a series of price functions to build a restructured graph that could be processed almost completely using Dijkstra's algorithm. This involved the random removal of paths with negative weights that would enable the source graph to be converted into a directed acyclic graph: one with only forward paths and no loops connecting the strongly connected clusters to each other. This form was selected because it opened the door to tools that would allow the use of the fastest algorithm. A later phase then reintroduces the missing negative-weight edges. The small number of these paths can be processed using the Bellman-Ford algorithm with comparatively little impact on runtime.