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]

(Later) Add to which their implementation of Bellman-Ford is stupid and doesn't terminate early once the distances stop changing. So it always takes Θ(mn) time even on graphs for which it should run much more quickly. —David Eppstein (talk) 07:14, 1 November 2009 (UTC)[reply]

Im the original person who posted the links (the time it was claimed to be spam). It was not spam it was part of many hours of research and surfing trying to find pages that seem to have an incomplete listed of resources. The links were all from many sources I felt, as a professional int he field, are important. You reverted my links and i let it stand even though i put hard work into it. Your revert was re-reverted here by someone else and you guys got into a revert war. I think its important these things are discussed, but your explanation constitutes Original Research so i must object. This library seems to hit on the top of google for many of the search terms i can come up with and yet there are no websites discrediting this source, and the project seems to have been open source for over 3 years. In the spirit of Wikipedia we should try to avoid original resource and use these other aspects to judge the resources we provide.98.23.60.15 (talk) 06:31, 1 November 2009 (UTC)[reply]

I don't see how the amount of effort you may have spent is relevant to whether these links are worth including. —David Eppstein (talk) 07:14, 1 November 2009 (UTC)[reply]