networkx/networkx — pull request #1118 by ysitu (2014-04-21 21:19:41+00:00)
Title: Add Goldberg–Radzik shortest path algorithm

The running time is *O*(*nm*). When applied to DAGs, the running time is *O*(*n* + *m*). Negative weights are supported.

The idea of the algorithm can be considered an extension of the predecessor heuristic in Bellman–Ford. Instead of inspecting the predecessors of the nodes individually, Goldberg–Radzik topologically sorts the nodes to scan (i.e., it handles their predecessors all at once). If topological sorting fails, a negative cycle is detected. Some literature finds this algorithm more robust than the Bellman–Ford algorithm.