Before revision:  where W is the absolute maximum weight of an edge in the graph . For sparse graphs, this improves over the best known running time for this problem and, by well-known reductions, also implies improved running times for the shortest path problem with negative weights, minimum cost bipartite \mathit{b}-matching when \|\mathit{b}\|_1 = O(m), and recovers the running time of the currently fastest algorithm for maximum flow in graphs with unit capacities (Liu-Sidford  ).
After revision:  where W is the maximum absolute value of any edge weight . For sparse graphs, this improves over the best known running time for this problem and, by well-known reductions, also implies improved running times for the shortest path problem with negative weights, minimum cost bipartite \mathit{b}-matching when \|\mathit{b}\|_1 = O(m), and recovers the running time of the currently fastest algorithm for maximum flow in graphs with unit capacities (Liu-Sidford ).