Talk:Johnson's algorithm

The algorithm is taken word for word from the second reference in case anyone wants to reword it or something. Fluxbyte (talk) 01:26, 1 April 2008 (UTC)[reply]

I've completely rewritten it. —David Eppstein (talk) 23:56, 4 April 2008 (UTC)[reply]

DANN

I removed a link to the DANN library, which claims to have an implementation of Johnson's algorithm. However, it has been spammed very recently to many Wikipedia articles. Additionally, it is a bad implementation: for each edge in the graph, it reweights it by finding a description of the entire path from the start vertex to each endpoint of the edge before calculating the weight of the edge. Although not an asymptotic slowdown because other parts of the algorithm are as slow in the worst case, this causes it to take O(n) per edge reweight step whereas the correct algorithm should just look up the weight and perform the reweight in constant time. The net effect is that even on graphs where the Bellman-Ford part uses few iterations (most of them), the reweighting part will slow it down. —David Eppstein (talk) 06:16, 1 November 2009 (UTC)[reply]