Talk:Dijkstra's algorithm
Latest comment: 14 years ago by GAMEchief in topic What does fi ; stand for
| This is the talk page for discussing improvements to the Dijkstra's algorithm article. This is not a forum for general discussion of the subject of the article. |
Article policies
|
| Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
Archives: 1, 2Auto-archiving period: 12 months  |
 | This article has not yet been rated on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||||||||||||||||||||
Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.
Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.
Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.
| |||||||||||||||||||||||||||||||||||||||||||||||
|
||
|
This page has archives. Sections older than 365 days may be auto-archived by Lowercase sigmabot III if there are more than 4. |
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 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. —Preceding unsigned comment added by 71.120.113.27 (talk) 15:09, 5 November 2009 (UTC)
- 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! 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? 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”.
- 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", ...). 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. 76.181.66.9 (talk) 15:31, 17 January 2010 (UTC) Dan
- 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.
- 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 would be .
- 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.
- 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, would be 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. 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 I talked about was for your changed graph. In the original, it really is and can be found directly using this algorithm. 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. —Preceding unsigned comment added by 76.181.77.83 (talk) 18:11, 18 January 2010 (UTC)
- I'll write it in detail: (“o” means that the node was already visited – is out)
- 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. —Preceding unsigned comment added by 76.181.77.83 (talk) 18:11, 18 January 2010 (UTC)
- No, you overwrite the distance of the neighboring node (B in the example), never of the current node. The I talked about was for your changed graph. In the original, it really is and can be found directly using this algorithm. Svick (talk) 17:42, 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, would be 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. 76.181.77.83 (talk) 16:57, 18 January 2010 (UTC) Dan
current 1 2 3 4 5 6 … 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. Svick (talk) 17:55, 21 January 2010 (UTC)
- thanks, I misread the last step in the algorithm section. It is very clear now. 76.181.66.9 (talk) 01:03, 22 January 2010 (UTC)Dan
- As you can see, the change of the distance of 5 occurs, when 4 is the current node. Svick (talk) 17:55, 21 January 2010 (UTC)
Greedy?
Within the description it says 'this is the "greedy" part, as described above'. 'Greed' is not mentioned before the description, probably an editing error. —Preceding unsigned comment added by 93.96.163.250 (talk) 17:31, 15 April 2010 (UTC)
What does fi ; stand for
in the code:
12 'fi' ;
What does this ''fi'' stands for? Ali Jamal--Ali Jamal 17:48, 8 December 2010 (UTC)
- It's an overly-cute but standard notation for the end of the block of code that begins with an "if". More specifically, it is "if" spelled backwards. —David Eppstein (talk) 17:54, 8 December 2010 (UTC)
- I move that it be changed to "end if," seeing as how that's what's used for "end for." -- Charles Stover 20:16, 8 December 2010 (UTC)