Talk:Dijkstra's algorithm: Difference between revisions

Revision as of 12:32, 7 April 2011

Revision as of 04:51, 8 April 2011

Line 15:

{{archives|auto=long|search=yes|bot=MiszaBot|age=365}}

== Pretty muddy ==

if you try to take the psudocode and directly turn it into code. Well by 5 lines an it fails. set all distance to infinity. Then you check to see if edge distance is infinity? ofc it was, you just set it to that, and now you exit. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/64.134.224.50|64.134.224.50]] ([[User talk:64.134.224.50|talk]]) 00:50, 21 March 2011 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

== Another interpretation of Dijkstra's Algorithm ==

Here is one way to find the shortest distance from s to every other vertex in the graph:

Let v be in G, and define o[v] to be the number of outgoing edges of v. Put o[v] little men on each each vertex v. These men are going to run a relay race. You fire the gun, and all the men on s start running at unit speed, one along each outgoing edge. Whenever a man reaches a vertex, all the men at that vertex run along the outing edges at unit speed. Notice that we are traversing all possible paths in the graph, and that the first man to get to vertex v gets there in the shortest time possible. Thus we've solved the problem.

Dijkstra's algorithm just simulates this process in discrete time intervals. The nth vertex added to S in Dijkstra's algorithm is the nth vertex reached by a little man.

I think this interpretation is very helpful in understanding the correctness of the algorithm. Should it be included in the article?

:Josh Brown Kramer [[User:129.93.181.31|129.93.181.31]] 21:11, 9 November 2006 (UTC)

This does not work, or it's not clear from your description that it works. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/71.120.113.27|71.120.113.27]] ([[User talk:71.120.113.27|talk]]) 15:09, 5 November 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

:: It's not bad, but a little unclear and a little misleading in its current form. It probably should say something like ''Let v be a vertex in graph G, s be the starting point and e be the ending point'' to introduce your terms. It should also read: ''For all v in G'' to indicate that all vertices have the little men and not just one vertex and I think where you write ''the first man to get to vertex v gets there...'' you mean to say something like ''the first man to get to vertex e'' or ''the first man to reach the destination''. You could also help clarify the paragraph by stating that the little men '''can only''' run at unit speed, thus avoid repeating the unit speed statement.

::Finally, your metaphor does not deal with the fact that "visited" vertices are not "revisited" by Dijkstra's algorithm. This difference wouldn't make much of a difference, as the little man on the fastest path will get there regardless of little men running across already visited links, but this distinction should be at least mentioned. Other than that, this metaphor does seem instructive and I think could help explain the article. If you want help coming up with some phrasing, feel free to leave a note on my talk page -- cheers! [[User:jheiv|jhe_{<small>iv</small>}]] ([[User_talk:jheiv |talk]]) 21:46, 6 January 2010 (UTC)

== Error? ==

Look at node 4. 22 < 11 + 9 is an error.

If you were to change the 9 on the top of the graph to some large value like 36 for example, the algorithm as stated wouldn't seem to find the shortest path. Also, if the graph were mirrored (3 nodes connected to the start become 6) and mirrored indefinitely, and then the 3 mirror initial path choices reduced in value by say, 5, it isn't clear that the algorithm would halt, or it would pick the right direction. Another variant of this is if I were to drop a branch down from the initial start node with a distance value 2, and then connect it back to node 2 with a branch distance value some really high value, say 81, it isn't clear the algorithm would pick the correct branch to travel on, even if it correctly calculates the shortest distance. I know I'm misunderstanding the essential algorithm somehow, but the stated steps seem to leave too much in question and differ substantially from Dijkstra's own set descriptions. (another problems seems to arise if you divide up all the branches in two by placing another node in between any two nodes. The algorithm could be tricked by having a low initial distance value and then a higher distance value on the second half, this is a variant of the first error). Whose version of this algorithm is this? Which of my objections has any merit? I hope none, because I really like this algorithm, but I can't seem to wrap my mind around these ideas. How does the algorithm handle dead ends and direction? [[Special:Contributions/76.181.77.83|76.181.77.83]] ([[User talk:76.181.77.83|talk]]) 00:47, 17 January 2010 (UTC) Dan

:In your first example, it would work correctly. Notice that the last comparison is 20 (4) >= 20 (5). That means the algorithm is trying to reach the target vertex even after it has a finite value.

:In all the other examples you're saying that it isn't clear what the algorithm would do, but from the instructions, it's clear what would it do in each step, so the final result is clear too. (The only exception is when you have two or more unvisited vertices with the same lowest distance. In that case, the algorithm works correctly, no matter which one you choose.)

:I'm really not sure what do you think is the problem. Maybe you could describe one of the examples you gave in more detail, what do you think would happen and what exactly is wrong, not just “I think it doesn't work”.

:[[User:Svick|Svick]] ([[User talk:Svick|talk]]) 01:35, 17 January 2010 (UTC)

:: It also might be helpful if you clarify what part of the article you have trouble with as there are a few that describe the algorithm (the sections "Algorithm", "Description of the algorithm", "Pseudocode", ...). [[User:jheiv|jhe_{<small>iv</small>}]] ([[User_talk:jheiv |talk]]) 04:28, 17 January 2010 (UTC)

:: I actually did describe several examples in detail, and I never said "I think it doesn't work" Not sure who you're quoting. In any case, I think it's best to deal with each of my objections piecemeal, so let's resolve each one in turn. Your first example high lights an inconsistency between the section "algorithm" and the graphic. The algorithm never has a step for comparing the source with the destination distance. If anything, read literally, the algorithm's last comparison before it halts would be to say 20<20+6, then it would not change 4's labeled distance and it would halt. At least at this fundamental level, how the graph and the section algorithm are written are inconsistent. Barring all of my other objections, this should raise a concern if the top 9 were changed to some horrendously large value like 50, the algorithm would successfully compare the distance through 3 to 6 and through 3 to 4, but would not compare the distance through 4 to 5 with distance through 6 to 5. When node 6 is current, we have what I have defined as a "dead end" comparison, where the algorithm is forced to conclude the minimal distance from target to source is 11+large number, say 11+50=61. So reading from the pseudocode section, the sequence S would incorrectly read {1,2,3,6,5} rather than the correct sequence {1,2,3,4,5,6}. I want to keep going, especially about how this gets to another ambiguity in the page, which is the difference between the pseudocode and the graphic and the description (why does it terminate at 5 being the last current node instead of 4? the algorithm finds the shortest distance path, independent of which node you choose as destination), but I feel these are probably quibbling details and the remainder of what I have discussed is interrelated with the first essential example. Thanks. [[Special:Contributions/76.181.66.9|76.181.66.9]] ([[User talk:76.181.66.9|talk]]) 15:31, 17 January 2010 (UTC) Dan

:::<small>I quoted you, but not exactly, you said things like “wouldn't seem to find the shortest path”. That's the same as saying that it doesn't work, but not explaining in detail why you think so.</small>

:::If the distance from vertex 6 to vertex 5 was 50, then, after visiting vertex 6, vertex 5 would really have a distance 61. But in the next step, unvisited vertex with the smallest distance would be 4, and the algorithm would change the distance of 5 to the correct value of 26 and <math>S</math> would be <math>\{1,2,3,4,5\}</math>.

:::I think I misunderstood what the animation meant by 20 (4) >= 20 (5). I thought it meant that the algorithm is trying to reach vertex 5 from 4, but in that case, there should be an arrow in the image and the vertex 4 should be marked as visited afterwards. What's really going on is that the algorithm chooses vertex 5 as the current node, because it has the smallest distance (along with vertex 4), and halts, because it's the target vertex.

:::[[User:Svick|Svick]] ([[User talk:Svick|talk]]) 10:57, 18 January 2010 (UTC)

:::: After some more careful thought on my part, the source of my confusion I think stems from the ambiguous wording of step 3 in the algorithm section. "For current node, consider all its unvisited neighbours and calculate their distance (from the initial node). For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 2, the distance to B through A will be 6+2=8. If this distance is less than the previously recorded distance (infinity in the beginning, zero for the initial node), OVERWRITE THE DISTANCE" (emphasis added) But which distance is being overwritten? I initially interpreted it as node B, or the non-current node connected to the current node because . This seems incorrect based on your last comment, and the version you understand makes much more sense than my interpretation. Another ambiguity is in regards to the first sentence: "calculate their distance (from the initial node)" which could mean sum all edge values connecting unvisited nodes to the current node with the current node's previously recorded distance. My proposed correction to step 3 is to have it worded thus: "For current node, consider each of its unvisited neighbors and calculate the distance (from the initial node). For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 2, the distance to B through A will be 6+2=8. If this value is less than the previously recorded distance of either the current node or the unvisited neighbor, overwrite that node's distance with this value." This certainly seems to handle the problematic case we had been discussing. However, I was reading your comment and seem to have stumbled upon yet another error in the article, this time with the pseudocode (or perhaps your interpretation of it). The actual correct sequence, <math>S</math> would be <math>{1,3,6,5}</math> as the shortest path from a to b in the diagram. Essentially, the order the nodes are visited in is not necessarily isometric to a subsequence of shortest path between two nodes! Djikstra's algorithm does what it is supposed to do, calculate minimum distances, but another program needs to interpret how to arrive at these distances. What makes the algorithm so powerful is step 5 (obviously in conjunction with the others) which causes the algorithm to examine the paths that seem shortest first and avoids endless permutations. Thanks. [[Special:Contributions/76.181.77.83|76.181.77.83]] ([[User talk:76.181.77.83|talk]]) 16:57, 18 January 2010 (UTC) Dan

:::::No, you overwrite the distance of the neighboring node (B in the example), never of the current node. The <math>S</math> I talked about was for your changed graph. In the original, it really is <math>\{1,3,6,5\}</math> and can be found directly using this algorithm. [[User:Svick|Svick]] ([[User talk:Svick|talk]]) 17:42, 18 January 2010 (UTC)

::::::Explain how this does not directly contradict "If the distance from vertex 6 to vertex 5 was 50, then, after visiting vertex 6, vertex 5 would really have a distance 61. But in the next step, unvisited vertex with the smallest distance would be 4, and the algorithm would change the distance of 5." The only way you can do this "after visiting vertex 6" is to change 5's distance when 5 is the current node. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/76.181.77.83|76.181.77.83]] ([[User talk:76.181.77.83|talk]]) 18:11, 18 January 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

:::::::I'll write it in detail: (“o” means that the node was already visited – is out)

:::::::{| class=wikitable

! current !! 1 !! 2 !! 3 !! 4 !! 5 !! 6

|-

| colspan=7 style="text-align:center" | …

|-

| 3 || 0o || 7o || 9o || 20 || ∞ || 11

|-

| 6 || 0o || 7o || 9o || 20 || 50 || 11o

|-

| 4 || 0o || 7o || 9o || 20o || 26 || 11o

|-

| 5 || 0o || 7o || 9o || 20o || 26o || 11o

|}

:::::::As you can see, the change of the distance of 5 occurs, when 4 is the current node. [[User:Svick|Svick]] ([[User talk:Svick|talk]]) 17:55, 21 January 2010 (UTC)

::::::::thanks, I misread the last step in the algorithm section. It is very clear now. [[Special:Contributions/76.181.66.9|76.181.66.9]] ([[User talk:76.181.66.9|talk]]) 01:03, 22 January 2010 (UTC)Dan

== Greedy? ==

Line 87 ⟶ 35:

== Wrong anim? ==

Look at the anim. First it goes to node #2. then when it wants to go to node #3 it count the length 9. it's absolutely wrong because if you want to go from #2 to #3 you must pass from a edge length 10. So what's the meaning of this? can anyone explain it for me? <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/109.162.218.57|109.162.218.57]] ([[User talk:109.162.218.57|talk]]) 12:31, 7 April 2011 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->