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]

The effort isnt what was important but rather the result of that effort. Firstly the effort consisted of finding generally well respected links I could. All the links (dANN included) were top hitting on google, seemed to have the most activity, the longest activity, and had no bad references I could find. In the case of the dANN link it seems to have received good attention, hits first on the relevant search terms, has public space for any objections or bugs to be shown, etc. The problems you speak of dont show up in the bugs section, anyone could have posted such a bug and had it reviewed. A proper way to debunk the viability of the library in a way that didnt show Original Research would be to point to various outstanding bug reports for this section of the source, or any source discrediting it really. You seem unusually defensive and i appologize if that is my fault, comments like that arent productive and didnt address my points.98.23.60.15 (talk) 07:23, 1 November 2009 (UTC)[reply]