Talk:Dijkstra's algorithm
From Wikipedia, the free encyclopedia
 |
This article is part of a WikiProject to improve Wikipedia's articles related to Computer science. For guidelines see WikiProject Computer science and Wikipedia:Contributing FAQ. |
[edit] Author credit
This may be a little controversial, but I think code should not include author credit or license in the same way ordinary article text does not. Any interested person can consult the edit history to learn the person who added it and e-mail them. For this reason I've removed the author credit. The code may also be edited by other persons, and so no longer be "owned" by the original author, or subject to their stated license. If you don't want to place your uncredited code in the article, I would be happy to replace it in its entirety with new code. Derrick Coetzee 17:55, 29 Oct 2004 (UTC)
- There's nothing controversial about that. It's Wikipedia policy that articles should not contain attributions to wikipedia contributors. (Obviously quotations of third party sources should be properly cited and attributed — but they should also follow proper guidelines regarding how much is quoted.
[edit] Diagram
I think this article could use a diagram, showing a simple edge relaxation or two. I'll make one sometime if nobody beats me to it. Deco 00:48, 9 Nov 2004 (UTC)
[edit] Sample Input Data
It would be nice if the code examples were all written to parse a common data sample and give consistent results; and if the data sample (something small like five nodes) was included and discussed in the text with a "desk check" walk through the algorithm.
I'll have to think about that.
[edit] Finding out the path in C implementation
It would be great if we can find out the path details inside the C code. The code that currently provided is only can calculate the shortest distance between the source and destination. --Shinjiman ⇔ ♨ 05:29, 31 May 2005 (UTC)
[edit] Set S not needed in implementation
The set S containing the vertices with known distances to the source is needed in the proof of correctness, but not needed in the actual implementation of the algorithm. Therefore, the two lines in the pseudocode initializing S and adding a vertex to S can be removed.
[edit] Pseudocode incorrect?
Perhaps I got something wrong, but I think the given algorithm doesn't really work in this way. When we first reach line no. 9, then all d[u]s are equal to infinity, except for d[s]. How can I choose the one from Q with the least d[u]? There must be at least an initialization step missing for those vertices that are adjacent to s.
Another point is that I can remember that there was a set containing vertices 1.) that are adjacent to a vertex for which the shortest path has been found and 2.) for which the shortest path has not been found yet.
I can't find it here...
- I'm adding the question back in, as it's an easy enough question to ask and it can't hurt to have an answer. s will be the first to be removed from the heap in the iterative step (note that s is included in the set of all vertices, Q). Each of its children will be updated, and the one reached by the lightest edge will be next from the heap...and so on.
- As for the second question, there's no need: each vertex is tested when it's reached. The conditional on line twelve will never be true if the shortest path has already been found. On the other hand, what you suggest is a possible optimization of the conditional: whenever a vertex is extracted from the heap, it is removed from the adjacency list of its predecessors. It's not clear whether this would be beneficial; in any case, doesn't change the worst-case time. --Mgreenbe 22:38, 27 January 2006 (UTC)
In addition to the above, the pseudocode appears to be inconsistent with the above description. It looks like the v's and u's are used in the opposite manner to what they are in the description. I'm still trying to get my head around the algorithm and I'm finding the inconsistencies quite confusing. --Bombastic 01:53, 18 October 2006 (UTC)
I think that one of the ways for the algorithm to be more understandable and for the article to appear more like the kruskal's algorithm and the prim's algorithm articles (which is a good thing) is to put the algorithm into a bullet format (in the introduction), rather than the inline text. Philomathoholic 05:39, 13 December 2006 (UTC)
[edit] What about non directed graphs?
I'm not sure that this algorithm couldn't be used on non directed graphs... For me it's quite obvious this algorithm can solve a problem like "shortest way between two towns"... And highways are rarely "one way", right? Can someone suggest a counterexample? --132.227.103.90 15:26, 28 March 2006 (UTC) Pronk
- An undirected graph is simply a directed graph with vertices connected by two edges, one for each direction. In geographic data sets, bi-directional roads are always represented as two seperate roads, one for each direction. So, it doesn't matter.
Anthony Steele I've implemented the pseudocode in c#, it works for me. The initialisation seems correct despite User:Mgreenbe's protestations, the start node will be the first node selected in line nine, since it has distance zero and the rest have +Infinity. The first set of outgoing edges followed will be from the start node, as it should be.
"previous[v]" is not needed if you just need the path length, not the actual route. Some error checking has been omittted, i.e. after line 9 you will have to check if there was any min node found. This will not be the case if the route you are trying to find does not exist. e.g. if the nodeas and paths are A->B and C->D, and you want a route from A->D.
[edit] Proof of correctness
I think that this article lacks the proof of correctness of the algorithm; more exactly, 'This vertex is chosen as the vertex with lowest value of d[u].' doesn't look so correct to me: it should be something like 'We know that we can move the vertex with the lowest value of d[u] from Q to S because...'. --Danmaz74 08:32, 3 April 2006 (UTC)
[edit] Negative Edge-weights
I think there is a problem with the following sentences:
"Unlike Dijkstra's algorithm, the Bellman-Ford algorithm can be used on graphs with negative edge weights, as long as the graph contains no negative cycle reachable from the source vertex s. (The presence of such cycles means there is no shortest path, since the total weight becomes lower each time the cycle is traversed.)"
I think there could be a shortest path from s to t even if there is such a cycle reachable from s, namely if there is NO path whatsoever from this cycle to the sink t.
[edit] 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)
[edit] 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)
