Content deleted Content added
move new comment and respond |
|||
Line 86:
for each edge (u, v) with weight w in edges:
in this line what is u ? I beleive u should be changed to i or vice versa. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/49.203.64.216|49.203.64.216]] ([[User talk:49.203.64.216|talk]]) 08:38, 25 May 2014 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
:If there are n vertices, the algorithm needs to iterate n-1 times (as in the given pseudocode), not n times (as your change would have it). It starts out with one vertex having the correct distance (the starting vertex) and each iteration adds one more, so only n-1 iterations are needed until all are correct. If you implemented it correctly the nth iteration would be useless. Further, the case where exactly n-1 iterations are necessary should be unusual: it only happens when the shortest path runs through all vertices and the order of relaxation within an iteration is backwards for the edges of this path. So I strongly suspect it is some other bug in your program. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 08:20, 24 November 2023 (UTC)
| |||