Talk:Dijkstra's algorithm: Difference between revisions
→Example size and heaps: new section
(→Example size and heaps: new section) |
|||
Line 8:
: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. --[[User:Spoon!|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. —[[User:Sonia|Sonia]] 00:30, 10 December 2011 (UTC)
| |||