Talk:Dijkstra's algorithm: Difference between revisions
more considerations to move this from draft
(more considerations to move this from draft) |
|||
Line 6:
:: I admit I didn't grok what distance metric you were using, so I ignored that part of your code. :-) In general though, I concur that a common example is a good idea. –[[User:Dkf|Donal Fellows]] 13:50, 25 January 2012 (UTC)
:The WP example just numbers the vertices, but I liked the way most solutions here use letters. The documentation requirement is something I've wanted on a number of other tasks. It should not only illustrate where variant algorithms exist, but help people comparing solutions recognize if two solutions implement the same algorithm or different variants. —[[User:Sonia|Sonia]] 18:52, 25 January 2012 (UTC)
:I'm floating a few more changes because it would be nice for this to come out of draft status looking all polished. I moved the documentation requirement to EC because I didn't want it to scare people from submitting initial solutions, and because I saw the tendency for documentation to get wordy. The directed/undirected point is important, and there's another point I'll give a new section below, single path/path tree. —[[User:Sonia|Sonia]] 21:25, 6 February 2012 (UTC)
== Java example cleanup ==
Line 32 ⟶ 34:
:Excellent point and something I failed to appreciate. I just looked at the picture and didn't read carefully. —[[User:Sonia|Sonia]] 18:40, 27 January 2012 (UTC)
:I just changed the task to specify a directed graph, and keeping the same example data, this changes the solution from acfe to acde, thus invalidating existing solutions. Sure the task could be written to keep acfe the correct solution, but I thought directedness was important enough to point out with a new solution. —[[User:Sonia|Sonia]] 21:25, 6 February 2012 (UTC)
== Single path / Path Tree ==
WP mentions the algorithm can produce a path tree, but discussions and examples tend to talk about single paths. I think it's fine for the task to ask for a single path solution, but now while it's in draft is the time for people to speak up for path trees if they like. Interestingly, Dijkstra's '59 paper doesn't mention path trees, but only the single path problem. (Problem 1 in the paper is a minimal spaning tree, which is something different.) —[[User:Sonia|Sonia]] 21:25, 6 February 2012 (UTC)
| |||