As discussed here Johnson’s Algorithm can be used to solve the APSP-Problem in $ O(V^2\log V + VE)$ in stead of $ O(V^3)$ for Floyd-Warshall. However, Johnsons Algorithm does quite a bit of work for the case that some weights are negative. Is there a faster way to compute this given that all weights are positive?