Talk:Dijkstra's algorithm

Description section issues

The section currently titled 'description' reads more like a tutorial on how to run Dijkstra by hand. It's full of second person and even tells you to use a pencil and follow along. Aside from that, it's just a complete restatement of the 'Algorithm' section, except in the context of city roads, jargon removed. It is of course necessary to provide an explanation that can be understood by the general reader, but this is redundant and not the way to do it. IntGrah (talk) 22:33, 26 April 2024 (UTC)

Algorithm > Pt. 4 (marking a visited) > claim of 'final and minimal'

Context: Responding to @IntGrah's edit's request to clarify why I feel that point 4 should refer reader to an aspect of point 5.

(Note that this is quite a fine detail of style, so probably not of big interest to most, but my edits were reverted, which suggest it had some importance to IntGrah).

The point 4 and 5 have a bit of a circular dependency which I will show below. Having said that, overall, I still think it's good that they are two separate points, because each information they give provides a new useful insight, but I see just one last fixable problem.

Namely, the claim of "distance recorded on the current node is final and minimal" does not yet follow from what the reader has read so far, especially that so far the reader does not know yet that there is going to be a loop, and how the 'current node' will change. It is only true thanks to the 5th point having "select the one with the smallest known distance" (if the step 5 selected any other node, it would not be true). I feel the insight of "this is the last time we are seeing this node" is helpful though, so I wouldn't remove it, but it would be helpful to admit, that this claim has not yet been justified, and point at where it will be justified, like I tried to do with 'see next step'. Otherwise the reader like me would stop and think they didn't understand something earlier. My new idea is, since @IntGrah points out it's not clear what aspect of step 5 is highlighted, that maybe it should explicitly state something like "(see next steps where the choice of next 'current node' always picks smallest distance)". Zlamma (talk) 12:30, 29 May 2024 (UTC)

It's important to note that this section is supposed to be a description of the algorithm, not a full fledged proof, so points which are justified inline with the algorithm should be brief. I think that the explanations you've written are a little too long. I understand your concern that the claim "final and minimal" is only justified in the next step; perhaps the earlier steps should deal with written to match the pseudocode more closely?

Currently, Step 2 says "Set the current node to be the starting node", Step 3 deals with the current node – "For the current node...", and Step 5 deals with the selection of the next node – "select the one with the smallest known distance".

To better approximate the actual algorithm, would you suggest rewriting Step 3 to be on the lines of "Select the unvisited node with the smallest distance to be the current node", remove the sentence from Step 2, and make Step 5 simply say "Go back to Step 3"?

With this structure, you could justify the points you made in step 4 much more concisely, rather than long proof sketches which refer to the next step. IntGrah (talk) 12:46, 29 May 2024 (UTC)

Your suggestions sound sensible to me. (Indeed I was trying to limit myself in the number of points changed, concerned that this would spark contention from many contributors that I would not be able to address, but collaboratively a change like this could be viable.)

Perhaps I would still add something like I wrote in bold here: "Select the unvisited node with the smallest distance to be the current node (on the first entry to this step, this is the starting node of distance zero)", just to make it easy to think about how the algorithm first engages the state, yet reaffirm that this is a universal instruction that handles all cases. Will leave it up to you though. Zlamma (talk) 13:35, 29 May 2024 (UTC)