Talk:Dijkstra's algorithm/Archive 1

Archive 1

Archive 2

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)

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)

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)

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.

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

Image encountered on Commons

Could this be useful?

The algorithm is wrong. The queue will become empty after first step. —Preceding unsigned comment added by 68.146.249.93 (talk) 03:46, 19 July 2008 (UTC) Leonard G. (talk) 02:58, 1 July 2008 (UTC)

To me, the colours seem both distracting and poorly chosen (the red is hard to read on the yellow-orange background). Oliphaunt (talk) 15:55, 1 July 2008 (UTC)

Undefined Terms

This article uses the terms "relax" and "relaxation" in a specific technical sense, but gives no definition. The use of undefined terms in mathematical writing is considered poor form. -- 172.191.112.126 (talk) 23:06, 25 February 2009 (UTC)

As far as I know, relaxation is well-defined within the field of mathematical optimization as a change of a problem which means that the set of feasible solutions increases of remains unchanged. --Joti (talk) 11:19, 30 March 2009 (UTC)

Implementation

See Wikipedia talk:WikiProject Computer science for the discussion concerning the removal of the code from this article. Probably we should discuss this specific case here and try to reach a consensus rather than continuing the edit war, but my position as that we should only include one code or pseudocode description of any algorithm, in as clear and humanly-understandable a language as possible — we are not a code repository and multiple implementations tell us more about the details of how to program in language X than about the algorithm itself. I also feel that this statement applies very well to the pseudocode and Python examples here — the pseudocode is clear and short, and while that's often true of Python it's less true in this case and the code is more about how to get around the limitations of heapq than about Dijkstra's algorithm. So I feel the pseudocode should stay and the Python should go. Offliner and CBM also both wrote comments over on WPCS stating that they felt the Python implementation should be removed from this algorithm — you can go over there to read their reasoning. —David Eppstein (talk) 15:45, 12 April 2009 (UTC)

Beat me to the punch. I was going to suggest this specific case be discussed here on its merits rather than to delete code based on a blanket assertion of consensus (and I can't say the discussion cited formed a clear consensus, it also conflated how much/what code with where did it come from). Since I had restored to the version you last edited and you're certainly an objective party here, I'm fine seeing you also support removal of the Python code. PetersV       TALK 16:12, 12 April 2009 (UTC)

Undirected graph

Why does the example of this algorithm only include undirected edges? As far as I know, the capability to handle directed graphs is what separates Dijkstra's algorithm from e.g. Prim's algorithm. --Joti (talk) 21:23, 12 May 2009 (UTC)

Even on undirected graphs, Dijkstra's shortest path algorithm and the Prim-Dijkstra-Jarnik minimum spanning tree algorithm compute different things. —David Eppstein (talk) 22:09, 12 May 2009 (UTC)

Link spam

I think links like this[1] should be removed immediately on sight. The site linked to is self-published and written by a student. Also, the IP of the anonymous editor who added it geolocates to the same area where the site author says he is from. The addition of this link seems like yet another attempt of advertisement. Please keep an eye out for this, and remove such links from other articles as well. Offliner (talk) 23:09, 22 June 2009 (UTC)

Response:

  Hi, sorry about the anonymous thing, I didn't notice I was logged off at the time of the edit. I just wanted to help out by posting a link to actual code. Don't get me wrong, the pseudocode is nice and all, but I think java and c++ users might benefit more from an example implementation. And finally, don't you think you are being a bit too hostile for such minor edit?  —Preceding unsigned comment added by Frankrod44 (talk • contribs) 23:55, 22 June 2009 (UTC) 

The same link has been added again. Please help in removing it or explain why it's justified. Offliner (talk) 18:47, 4 July 2009 (UTC)

Why it's justified: The link contains a clean and commented implementation in both Java and C++ of Dijkstra's Algorithm being used for two different purposes, to find the shortest path from one node to another, and to find the shortest path from one node to all others. As author of the code I can tell you that it has been tested against 3 different online judges and managed to pass them all. You can review the code for correctness if you like. Any optimizations would be gratefully accepted. Frankrod44 (talk) 21:40, 4 July 2009 (UTC)

Google searching finds about two million hits for "Dijkstra implementation". What argument can you make that, among those two million, yours should be one of the half-dozen or so that we have room to list in this article? I don't want to know why yours is a good implementation, I want to know why it's so spectacularly good that it beats out the other 1,999,990. —David Eppstein (talk) 21:52, 4 July 2009 (UTC)

Clearly, the argument that you ask for is near impossible. It would require me to examine approximately two million sites. That I do not have the time for, and I suspect that neither did those who chose the 9 links that are currently there. So why have pose such a requirement for only this link?

What I have noticed though is a lack a variety in the external links section. Truth is that most of the current external links are applets and animated pictures of Dijkstra's algorithm. While these applets are nice, we don't need 4 or 5 of them showing the exact same algorithm, just 1 or maybe even 2 if we really can't make up our mind. However, the external links section does lack nice, short, readable code (that you don't need to register an account to download or copy). The first link, in my opinion, is a great example of code thats easy to read and learn from. However it is limited to C users, that is why I thought mine could help it could do the same for Java and C++ users. And best of all, it is not cluttered with graphics code, so it is ready to be used.

While I can't prove that it is the best implementation you can find, I think that it gets the job done. Personally, I wish someone had shown me that code while I was trying to learn the algorithm, it would have made more sense that some of those long overly specialized source codes I found through Google. So what do you think?

Frankrod44 (talk) 23:41, 4 July 2009 (UTC)

Rename page to 'Moore-Dijkstra algorithm'?

I have been reading around the subject and have come across a paper by Robert Dial that includes a description of what appears to my untrained eyes to be the same algorithm credited to an E.F.Moore.

The Dial paper I refer to is: Robert B. Dial, Algorithm 360: Shortest-path forest with topological ordering [H], Communications of the ACM, v.12 n.11, p.632-633, Nov. 1969

The citation in Dial's paper to Moore is: Moore, E. F. The shortest path through a maze. In International Symposium on the Theory of Switching Proceedings. Harvard U. Press, Cambridge, Mass., hpr. 1957, pp. 285-292 - notably two years earlier than Dijkstra's 1959 paper.

I have not read the Moore paper but have seen references elsewhere on the internet to the Moore-Dijkstra algorithm. Can anyone confirm whether the Moore and Dijkstra algorithms are effectively the same? —Preceding unsigned comment added by 82.152.45.26 (talk) 22:42, 3 August 2008 (UTC)

I haven't seen citations of Moore for this algorithm, but it many algorithms have been independently discovered by multiple authors, and sometimes only one author is credited—not necessarily the earliest one. Anyway, if it's true that Moore described an equivalent algorithm, it still should be determined (in my opinion) whether the reference to Moore occurs often enough in the literature that the page can be renamed. I think it's no problem to mention it right now in the article lead. Oliphaunt (talk) 07:15, 4 August 2008 (UTC)

Articles should be named by the name by which they are most commonly known. Even if the name you suggested were in use, the current name is the most widely-known one by far, being the name used in many prominent textbooks. It's not Wikipedia's job to "give credit where credit is due," only to describe. Dcoetzee 10:33, 4 August 2008 (UTC)

Added a line in the Lead on Moore's (1957) equivalent algorithm. This is long overdue. Sniedo (talk) 02:00, 21 August 2009 (UTC)

Dynamic programming perspective

I added a short section entitled "A dynamic programming perspective. More on this at here ...

Sniedo (talk) 03:37, 16 August 2009 (UTC)