Content deleted Content added
m Signing comment by 125.239.41.100 - "" |
move new comment and respond |
||
Line 14:
}}
{{Archive box|auto=yes}}
== Pseudocode bug? ==▼
The pseudocode in the article states:▼
for i from 1 to size(vertices)-1:▼
I'm pretty sure that it's supposed to be▼
for i from 0 to size(vertices)-1:▼
or, equivalently▼
for i from 1 to size(vertices):▼
The program I made based on the pseudocode didn't work until I made this change. Can anyone confirm that this is indeed the case (and not just some other bug in my program) and if so, correct the article? --[[User:Smallhacker|Smallhacker]] ([[User talk:Smallhacker|talk]]) 15:38, 3 March 2011 (UTC)▼
One more clarification on the Pseudocode▼
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-->▼
==== proposed answer ====
Line 86 ⟶ 71:
:Let's wait until it's at least been accepted to a conference before adding anything here. Anyway, the right place is [[Shortest path problem]], because it's a different algorithm than BF. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 05:02, 8 November 2023 (UTC)
▲== Pseudocode bug? ==
▲The pseudocode in the article states:
▲ for i from 1 to size(vertices)-1:
▲I'm pretty sure that it's supposed to be
▲ for i from 0 to size(vertices)-1:
▲or, equivalently
▲ for i from 1 to size(vertices):
▲The program I made based on the pseudocode didn't work until I made this change. Can anyone confirm that this is indeed the case (and not just some other bug in my program) and if so, correct the article? --[[User:Smallhacker|Smallhacker]] ([[User talk:Smallhacker|talk]]) 15:38, 3 March 2011 (UTC)
▲One more clarification on the Pseudocode
▲ 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. 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)
| |||