Content deleted Content added
Fixed {{Vital article}}; WP:TALKORDER |
|||
Line 23:
::Can confirm that this doesn't work if implemented as written in the article right now. I am busy doing something and won't be fixing the article; whoever's reverting it when other people fix it needs to stop. <!-- Template:Unsigned IP --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/174.34.23.247|174.34.23.247]] ([[User talk:174.34.23.247#top|talk]]) 23:11, 29 November 2019 (UTC)</small> <!--Autosigned by SineBot-->
: To answer the question: Yes, the main function is correct. The web reference that goes with the pseudocode uses a <code>path</code> array, but this article uses a <code>next</code> array. This is not just a difference in naming; the variables are used for different things. Specifically, <code>path[u][v]</code> answers the question "on the shortest path from ''u'' to ''v'', which vertex will be visited '''last''' (before arriving at ''v'')?" Whereas <code>next[u][v]</code> answers the question "on the shortest path from ''u'' to ''v'', which vertex will be visited '''first''' (after leaving ''u'')?"
: This is why <code>path</code> from the web reference is initialized as <code>path[u][v] = '''u'''</code> for all edges ("on a direct connection from ''u'' to ''v'', we must have come from ''u''"), but <code>next</code> in the article is initialized as <code>next[u][v] = '''v'''</code> ("on a direct connection from ''u'' to ''v'', we first go to ''v''").
: This difference in data representation has two consequences when it comes to reconstructing the full path:
# The main loop in the <code>PrintPath</code> procedure from the web reference keeps checking <code>Path[source][destination]</code>. The value of <code>source</code> is constant, but <code>destination</code> is updated continuously. This is because <code>Path</code> essentially encodes the path information backwards: At each step we have to ask, "on the shortest path from <code>source</code> to <code>destination</code>, what was the '''last''' vertex we visited (before reaching <code>destination</code>)? And before that? And before that? And before that?" ... until we have retraced our steps all the way back to <code>source</code>, at which point the loop stops. <br> On the other hand, the main loop in the <code>Path</code> procedure from the article keeps checking <code>next[u][v]</code>. Here the value of <code>v</code> (the destination) is constant, but <code>u</code> (the source) is updated continuously. This is because <code>next</code> encodes the path information forwards: At each step we ask, "on the shortest path from <code>u</code> to <code>v</code>, what is the '''first''' vertex we have to visit (after leaving <code>u</code>)? And after that? And after that?" ... until we reach our destination <code>v</code>, at which point the loop stops.
# Since <code>PrintPath</code> from the web reference reconstructs the path backwards, it has to use a stack to reverse the order of visited vertices (LIFO). That's why there is a second loop in that code. But the <code>Path</code> procedure in the article works forwards, so it can just append each segment to the <code>path</code> variable as it goes.
: [[Special:Contributions/84.149.142.109|84.149.142.109]] ([[User talk:84.149.142.109|talk]]) 11:30, 28 December 2022 (UTC)
==Is there a bug in the main loop? ==
| |||