Anonymous user
Talk:Dijkstra's algorithm: Difference between revisions
→Example size and heaps
m (→Example size and heaps: slipped, not *planar*) |
|||
Line 15:
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)
: <s>21k nodes, but how many edges?</s> NVM, only 240k edges, which is low (a normal graph expects edge count to be somewhat comparable to V<sup>2</sup>, 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?) --[[User:Ledrug|Ledrug]] 00:40, 10 December 2011 (UTC)
: Some possibly relavent points: 1) The Go code spent most of its time matching strings to find overlaps, that's O(n^2) with n = 20k ish; 2) the edge count is relatively low, and the code stops after reaching the target node (instead of finding the distances to all nodes). It is a valid use of the algorithm, but since the edge count isn't high and there are some peculiarities in the way distances are computed (nodes of long words tend to have longer distances to everything else, and low edge count makes the graph more tree like which sort of forces the search to follow a narrow path), the program didn't have to search too much to finish. Of 20k ish nodes, it only need to navigate through 2820. 3) minor: the tree doesn't seem to be fully connected. There may be a small number of nodes not reachable from the starting point.
: The Go code is fine for what it's doing, but it's best not to draw conclusions about the performance based only on the current test case. --[[User:Ledrug|Ledrug]] 06:55, 10 December 2011 (UTC)
| |||