Talk:Dijkstra's algorithm
From Wikipedia, the free encyclopedia
 |
This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions. |
| Start | rated as Start-Class on the assessment scale |
| Mid | rated as Mid-importance on the assessment scale |
[edit] Confusing Comment
What does this mean on line 8 of the algorithm? What two nodes? What new graph?
// Remove and return best vertex from nodes in two given nodes
// we would use a path finding algorithm on the new graph, such as depth-first search.
[edit] Moochie Moocherson??
what's this about? I don't wanna comb this for vandalism, is there a way to just mark it as vandalized? ThomasGHenry (talk) 02:36, 25 February 2008 (UTC)
[edit] Bad grammar and is it even true?
The article states "This algorithm was latter approved logically by Dr Saiful Islam, a Phd Advanced researcher from Greenwich in 2007 after conducting many studies within the feild of computer networking." Seems like this chap added this himself- surely it should be removed. 18:27, 20 May 2007 (UTC)
[edit] EWD would have cried
The links to the animations are extremely questionable. If the king had seen an an animation of Pythagoras' theorem would that have made him a master of Geometry? "There is no royal road to Geometry", Edsger W Dijkstra [EWD xxxx]
62.251.121.16 21:02, 9 March 2007 (UTC)
[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)
There should be a table of diagrams to illustrate the algorithm, not a lay description (or if the lay description remains, all algorithm articles should have one for continuity). See Prim's algorithm for what I suggest. —Preceding unsigned comment added by 194.81.36.61 (talk) 15:29, 9 June 2008 (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.
-
- Sort of, if in each step you're going to check each vertex not in S. But that is inefficient. When you queue the vertices you would have a representation of S with the distances in the priority queue. I think that this, and the sometimes confusion about greedy algorithms which the gentleman refers to below, cause laymen and even some textbooks to present erroneous descriptions of this algorithm. With that in mind - and I wouldn't dream of touching the mathematical formulations presented here - may I suggest adding a description of the algorithm in laymen terms which is more easily understandable?
-
- Using the street map, you're marking over the streets (tracing the street with a marker) in a certain order, until you have a route marked in from the starting point to the destination. The order is conceptually simple: from all the street intersections of the already marked routes, find the closest unmarked intersection - closest to the starting point (the "greedy" part). It's the whole marked route to the intersection, plus the street to the new, unmarked intersection. Mark that street to that intersection, draw an arrow with the direction, then repeat. Never mark to any intersection twice. When you get to the destination, follow the arrows backwards. There will be only one path back against the arrows, the shortest one. I think that's much simpler and intuitive for a layman.
-
- Naturally, keeping a list of the distances to the intersections, and keeping it sorted, is going to eliminate a lot of work, making it faster and easier. That's the "Set S" - or "priority queue" when sorted - may not be strictly necessary to solve the problem but it should be part of the algorithm. Wphamilton 20:46, 17 September 2007 (UTC)
[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.
- So the pseudocode should be:
7 while Q is not empty: 8 u := extract_min(Q) 9 if u not found 10 break // or something more pseudocode like
This way it will work for not connected graphs. Hrvoje Prgeša (talk) 17:13, 7 May 2008 (UTC)
[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)
[edit] Djikstra Implementation With PHP
I'm trying to create Djikstra Algorithm implementation with php. I've made djikstra function which input parameters are :
1. $G as array of graph weight
2. $s as initial node
3. $f as final node
and the output is assosiative array Array["length"] and Array["path"]
And the function is :
<?php
function djikstra($G,$s,$f){
$d = array();
$prev = array();
$Q = array();
foreach($G[$s] as $key=>$b){
$prev[$key] = 0;
$d[$key] = $G[$s][$key];
$Q[]=$b.":".$key;
}
$d[$s]=0;
$S = array();
while(count($Q)>0){
asort($Q);
$u = array_shift($Q);
$u = explode(":",$u);
$S[] = implode(":",$u);
foreach($G as $k=>$z){
foreach($z as $l=>$w){
if($d[$k] + $w < $d[$l]){
$d[$l] = $d[$k] + $w;
$prev[$l] = $k;
}
}
}
}
$stop = false;
$jalur = array();
while(!$stop){
if($f == $prev[$f]){
$stop = true;
}else{
$jalur[] = $f;
$f = $prev[$f];
}
}
$jalur = array_reverse($jalur);
array_unshift($jalur,$f);
return array("length"=>$d,"path"=>$jalur);
}
?>
And below is the example of implementation of the function
<?php
$L = array(
0 => array(999, 1, 4, 999, 999, 999),
1 => array(1, 999, 2, 7, 5, 999),
2 => array(4, 2, 999, 999, 1, 999),
3 => array(999, 7, 999, 999, 3, 2),
4 => array(999, 5, 1, 3, 999, 6),
5 => array(999, 999, 999, 2, 6, 999)
);
$d = djikstra( $L, 0, 5);
print_r($d);
?>
Comments and suggestion will be gladly accepted. Contact me at al1412 [at] gmail [dot] com
--Al1412 10:19, 31 December 2006 (UTC)
[edit] Dijkstra's Algorithm Cannot Be Implemented With Priority Queues
Many books on data structures & algorithms state that Dijkstra's Algorithm can be implemented using priority queues. This is not true. The problem is that items that are stored in the priority queue need to have their priorities changed dynamically as the algorithm progresses. A priority queue, the kind that is implied by these books, does not allow dynamic modification of priorities. Only certain types of heaps allow incremental change to priorities of elements in the heap.
J.C. Jones 02:26, 8 January 2007 (UTC)
- According to "Data structures and problem solving using Java" (by M. A. Weiss), you can use a standard priority queue by systematically queuing a vertex each time its value is lowered. Then, when you dequeue, you skip any vertex which has already been processed. Since the size of the queue is bounded by |E|, and there are at most |E| insertions / deletions, the running time is O(|E| log |E|) -- Olivier 16:21, 27 February 2007 (UTC)
[edit] Set S during the algorithm
The algorithm maintains two sets of vertices S and Q. Set S contains all vertices for which we know that the value d[v] is already the cost of the shortest path
Hmm, really? To me, it rather looks like the following is true:
The set S is such that, after each finished for-loop (line 11-14), for any vertex v in S, the value d[v] is the cost of the shortest path to this vertex which lies inside S (e. g. of the shortest among all paths all of whose vertices belong to S).
But there may be a shorter path containing some vertices not in S. Of course, at the end of the algorithm, all vertices are in S, so we really know the shortest paths to each of them - but only at the end of the algorithm, not before. Thus, we can not stop in the first moment we reach the destination vertex - well, we can stop, but the path we obtain will not necessarily be the optimal one.
Do I misunderstand something about the algorithm? - darij
Ok, I was. It was in the meaning of u := Extract_Min(Q). Still I'd say this should be somewhat precised in the pseudocode, e. g. by saying u := Extract_Min(Q,d). - darij
[edit] Initialization of d[]
"Initially, this value is 0 for the source vertex s (d[s]=0), and infinity for all other vertices, representing the fact that we do not know any path leading to those vertices (d[v]=∞ for every v in V, except s). "
That's not quite true - the path from s to s is not necessarily 0. Z
- No? Could you give an example where the shortest path from a point to itself is not 0?--bb 17:00, 21 August 2007 (UTC)
[edit] It's not greedy, is it?
Hi, all. In the begining it is said that the Dijkstra's algorithm is a greedy one. But I don't think so. Dijkstra's algorithm is an algorithm with dynamic programming approach. When finding which path to go from the ith node to the destination, it's considered that which path from the ith node to the destination is the shortest. But in greedy approach, it is considered that which neighboring node is nearest. -- Ephesians 4:31, 8 June 2007 (UTC)
[edit] Why can't this algorithm be used with negative paths?
Someone needs to explain this in the article, because the algorithm does work for a good many graphs with negative paths. It would also help people gain a better understanding of the algorithm. Fresheneesz 20:07, 3 December 2007 (UTC)
- All this would require is a single motivating example of a graph with negative paths where the algorithm produces incorrect results or fails to terminate. I'll ponder something... Dcoetzee 23:10, 3 December 2007 (UTC)
[edit] Diagram
I created the shown diagram for use in this article. I'll consider how best to incorporate it. I thought I'd added it before at some point. Dcoetzee 19:19, 15 January 2008 (UTC)
[edit] Article should mention "Shortest path tree"
Since this algorithm outputs a Shortest path tree, it would be nice if the article said so, with the appropriate link.
MusicScience (talk) 08:42, 17 January 2008 (UTC)
- I agree. Dcoetzee 09:05, 17 January 2008 (UTC)
- OK, I've adding "outputting a Shortest path tree" to the first sentence of the article. —Preceding unsigned comment added by MusicScience (talk • contribs) 09:01, 22 January 2008 (UTC)
[edit] Discoverer?
Or inventor? Are algorithms discovered or invented? I think it would have to be the latter.--88.149.234.141 (talk) 03:23, 17 February 2008 (UTC)
- That's a philosophical question (ref Platonic idealism) that I hope we could resolve in some kind of computer science or mathematics manual of style. I went with "conceived". Dcoetzee 06:53, 17 February 2008 (UTC)
gand marao saalo............kisi ko kuch nai aata hai....... —Preceding unsigned comment added by 61.17.223.46 (talk) 18:56, 27 April 2008 (UTC)
[edit] Lay man's description doesn't make sense
The order is conceptually simple: from all the street intersections of the already marked routes, find the closest unmarked intersection - closest to the starting point (the "greedy" part). It's the whole marked route to the intersection, plus the street to the new, unmarked intersection. Mark that street to that intersection, draw an arrow with the direction, then repeat.
I read this paragraph 10 times, and this makes no sense. It needs to be explained in more clear, precise steps. Superjoe30 (talk) 01:13, 20 May 2008 (UTC)
hey, now I get it! I just had to read it 35 times and try it out on paper. Maybe I'm just slow. Superjoe30 (talk) 04:18, 28 May 2008 (UTC)
