Content deleted Content added
Fixed {{Vital article}}; WP:TALKORDER |
|||
Line 69:
And what do the thick arrows and grey vertices mean? Are they the vertices we already have the final distances of, and the shortest paths leading to them? The problem with this is that the algorithm is not supposed to "know" these at that point - if we stop there, we cannot be sure that we would not get better results (shorter paths) for these vertices in a later step.
==== Thoughts by another editor ====
I agree with the confusion. I believe that v3 and v4 incorrectly update. There is no possible path by which the cost to v4 is 4, so there's no way the algorithm should ever update the weight to 4. And like the parent said, the algorithm should never increase the weight, so v3 shouldn't temporarily change to 6 and back to 4. I think the original creator of the gif simply swapped the two values by accident.
It also converges after 3 cycles, which is common for this algorithm. In fact, this algorithm can converge after 1 cycle, if the optimal path is (randomly) selected.
I think removing the bold edges, darkening of the vertexes, and stopping the animation after the 3rd frame would really help this page, but I didn't make the change in case I misunderstand the algorithm.
P.S. First comment. Please don't bite the newcomer. I couldn't find a way to comment on the original post so I added to it.
[[User:Lothsahn|Lothsahn]] ([[User talk:Lothsahn|talk]]) 21:47, 31 October 2021 (UTC)
| |||