Talk:Dijkstra's algorithm
Java example cleanup
I've done some cleaning up of the Java example, making many of the problems in the code much less prominent. (For example, I've reduced the use of effectively-global variables and I've split the I/O from the algorithm.) More work is needed to finish transforming it from something that stank of old-skool C, but it's a long way there. I've not really addressed any of the issues raised in the alertbox (e.g., the arbitrary node limit is still there — not that you'd want to have to type in the distance matrix for anything that large anyway) but they should now be much easier for someone else to address. –Donal Fellows 03:22, 9 December 2011 (UTC)
Floyd–Warshall
The "Floyd–Warshall algorithm" is also interesting, from a graph comparison point of view, since it finds all shortest paths in a graph in O(|V|^3) time, where the most highly optimized version of Dijkstra's algorithm requires O(|E| + |V| log |V|) for a path and there are O(|V|^2) potential paths. --Rdm 20:47, 9 December 2011 (UTC)
- Feel free to start a task for it. Many of these algorithms have been listed on Rosetta Code:Village Pump/Suggest a programming task but nobody has taken the initiative to start them. --Spoon! 22:47, 9 December 2011 (UTC)
Example size and heaps
I posted a couple of ideas. The WP data seems an obvious choice for the basic task. I experimented some with large graphs. My first implementation wasn't heap based and I was surprised that it could handle graphs of a few thousand vertices. I was also surprised that my heap based version only ran about 12 times faster for a graph of this size (21K nodes.)
Given how well the O(n^2) algorithm works, it should be fine for the basic task and I don't think we should fuss that it's inefficient. The heap enhancement makes a nice requirement for extra credit. To show it off seems to require a really big graph though! This thing with unixdict.txt is what I came up with for something that is repeatable. —Sonia 00:30, 10 December 2011 (UTC)
21k nodes, but how many edges?NVM, only 240k edges, which is low (a normal graph expects edge count to be somewhat comparable to V2, your graph is only about 1/2000 of that, which is to say, instead of a web, that graphis is more like trees: very few loops (is it guaranteed to be connected?) --Ledrug 00:40, 10 December 2011 (UTC)