Talk:Dijkstra's algorithm/Archive 1

This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

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

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)

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.

—Preceding unsigned comment added by 67.180.48.37 (talk) 00:56, 12 June 2008 (UTC)

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. —Preceding unsigned comment added by 216.240.40.182 (talk) 01:48, 18 April 2005 (UTC)

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.—Preceding unsigned comment added by 141.20.24.112 (talk) 10:38, 23 June 2006 (UTC)

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—Preceding unsigned comment added by 84.163.6.224 (talk) 22:44, 30 March 2007 (UTC)

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—Preceding unsigned comment added by 84.163.16.137 (talk) 08:38, 31 March 2007 (UTC)

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 04:31, 8 June 2007 (UTC)

Animation Infobox Mistake

When considering a path from node 3 to node 6, the image quickly displays "14 < 9+2" over node six, before replacing the value with "11". The right value is displayed over node 6, but the inequality is clearly wrong. —Preceding unsigned comment added by 24.253.131.109 (talk) 20:48, 3 September 2009 (UTC)

Also consider the path from node 2 to node 4, the inequality "22 < 11+9" is displayed over node 4. Again, the correct value is selected, but the inequality is incorrect. —Preceding unsigned comment added by 71.120.113.27 (talk) 14:46, 5 November 2009 (UTC)

Return Value

Shouldn't the pseudocode return previous[]? The algorithm should return something from which we can determine the shortest path to a node, but distance[] (the value currently returned by the pseudocode) just holds the length of the path, not the path itself. previous[], on the other hand, holds a direct predecessor for each node in the graph, which can be used to create the required paths.

e.g. Using the final value of previous[] from the animation, which is

{undefined, 1, 1, 3, 6, 3}

So if I want to know the shortest path from node 1 to node 5, I look at node 5, see that it's predecessor is 6. So I go to 6 and see its predecessor is 3, which has a predecessor of 1. So my path (when reversed), is 1 -> 3 -> 6 -> 5

distance[], on the other hand, holds the following values:

{0, 7, 9, 20, 20, 11}

This doesn't tell me where to go at any particular point, just that the shortest path to node 5 has a weight of 20.

Having never edited a page before, I was reluctant to just jump in and change it. If someone could confirm that what I've said is correct, I'll change the pseudocode.

--Satyr216 (talk) 00:42, 19 November 2009 (UTC)

The task is often given as finding the distance to a node, so returning distance[] is the correct solution. On the other hand, in practice, you usually need both the distance and the path with that distance and returning only previous[] wouldn't be sufficient in that case, so I think the current solution is a reasonable one.

By the way, don't feel reluctant to edit an article. You should be bold and change it to what you think is correct. Svick (talk) 09:54, 19 November 2009 (UTC)

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! jhe_iv (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", ...). jhe_iv (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

S

would be

\{1,2,3,4,5\}

.

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,

S

would be

{1,3,6,5}

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

S

I talked about was for your changed graph. In the original, it really is

\{1,3,6,5\}

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)

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

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)

Python code

According to WP:NOTREPOSITORY, the python code should not be here. I suggest that it be deleted soon. Please discuss it below. - Subh83 (talk | contribs) 17:29, 18 April 2011 (UTC)

I don't agree that Python code is never justified on Wikipedia — often it can make a good alternative to pseudocode as a way of communicating the essence of an algorithm. But in this case I don't think it adds much to the pseudocode that is already here, especially since the style of writing gives up most of the advantages of conciseness and readability that Python usually has. So in this case I agree that it should be deleted. —David Eppstein (talk) 18:03, 18 April 2011 (UTC)

Removed it.
Although I agree Python codes are quite intuitive in general, I am not sure if any specific language should be preferred since may programmers may not use that language and may be unfamiliar with the specific syntaxes. Also, preferred syntaxes may vary between versions of the programing language (Wikipedia:Algorithms_on_Wikipedia). - Subh83 (talk | contribs) 22:25, 18 April 2011 (UTC)

Running Time

The running time is mentioned as O((|E| + |V|)log |V|) if binary heap is used. I think it assumes Relax(v) = log|V|, but with real binary heap, the operation is "remove v from heap" and "re-add v" are O(|V|) and O(logV), resp., making Relax(v) = O(|V|). Hence, the total running time should be O(|V|log|V| + |E||V|). Can someone verify? -- Naba Kumar (talk) 21:21, 26 May 2011 (UTC)

Removing an element from binary heap takes logarithmic time, so the bound in the article is correct. -- X7q (talk) 21:57, 26 May 2011 (UTC)

Removing an element (in this case, a vertex) requires finding it first, which is O(|V|), not O(log|V|) - note: you don't know the index. Relax(v) can alternatively be defined as = find key (O(|V|)) + decrease-key (O(log |V|)) = O(|V|) -- Naba Kumar (talk) 22:13, 26 May 2011 (UTC)

If you don't know the index and have to search sequentially for it, you're doing it wrong. In this case, you do know the index: it's always at the front of the heap. And more generally if you want to find the position of a vertex in a heap (say for decrease key operations) you can simply maintain an index for each vertex that stores its position in the heap, and change these indexes whenever you change the heap. —David Eppstein (talk) 22:52, 26 May 2011 (UTC)

The decrease-key operation I pointed out is not about removing from top, but a step that happens in between step 16 and 19 in pseudo code (it's implied, but rather should be written down for clarity). Also, it's not about being "wrong". Removing a non-min element from a binary heap can not be done below O(n) without datastructure augmentation as you just described, in which case the statement in the article "With a binary heap, the algorithm requires O((|E| + |V|)log |V|) time ..." is therefore wrong verbatim when applied to the pseudo code. At best, it's insufficient to describe a casual reader how one arrived at O((|E| + |V|)log |V|) as algorithm's performance. I think, the article should make this clarification and mention performance of both non-augmented and augmented structure. Naba Kumar (talk) 10:03, 28 May 2011 (UTC)

Okay, I have fixed the article by (1) adding step 19 explaining the need of decrease-key operation and (2) explaining runtime with and without the extra indexing. I believe this is much more clear now. Thanks for you inputs. Naba Kumar (talk) 10:27, 28 May 2011 (UTC)

I don't think we need to list that suboptimal time. No one implements Dijkstra in that way. It's worse than Dijsktra without a heap (O(V^2) is better than O(VE + whatever) for connected graphs). A note explaining that an array of indexes into the binary heap is required to achieve stated time bounds would be useful though -- X7q (talk) 10:53, 28 May 2011 (UTC)

Agreed. I just rephrased it better. Naba Kumar (talk) 15:52, 28 May 2011 (UTC)

In addition, with a "vanilla binary heap" without the reverse index, it is still easy to get O(m log n) time: simply re-insert the vertex after each decrease-key ignoring the fact that it already has another entry in the heap, and check whenever you do a delete-min whether it's a vertex you've already seen. The disadcantage of doing it this way is primarily space (you get a heap entry per edge rather than per vertex). —David Eppstein (talk) 15:41, 28 May 2011 (UTC)

I don't think that works in practice because the vertex being referenced by both the entries (the newly inserted and the old one) are indistinguishable since they are the same, and the "old one" is quite likely already in the wrong place in the heap because of the change in it's value. In addition, simply being just seen-before is probably not enough distinction because a vertex can possibly be decreased-key more than once (so a count is needed, rather than a flag). The reverse index approach is a sensible approach I see (albeit a bit dirty because you break abstraction of the Queue object by storing Queue data inside Vertex structure without having to resort to an external hashtable of vertex->heap_index). I hope someone identifies a cleaner data structure to use for the Queue instead of binary heap. Kh naba (talk) 16:12, 28 May 2011 (UTC)

It does too work. I've implemented and tested it. You just have to ignore heap entries whose priority is larger than the already-determined distance for a vertex. And the reverse index is not only "a sensible approach", it is exactly the standard approach. —David Eppstein (talk) 16:21, 28 May 2011 (UTC)

Hmm, so you kept priorities to be separate from vertex min-distances, something like Q = [.., {v1, p1}, .. {v1, p2}, ..] and v1=[min_distance, previous ...]? That would certainly work. I had the queue totally depended on the vertex structures, like Q = [... v1, ... v1, ....] and v1 = [min_distance, previous, ...]. There, it doesn't work because min_distance is the priority in both instances of v1 - as seen by the queue. Your approach is clearly better (although it introduces additional structure {v,p} to hold the queue, but that's better than the reverse-index approach). Why not describe it in the article/pseudo-code so that others could follow it? -- Naba Kumar (talk) 19:24, 28 May 2011 (UTC)

And thanks for pointing out this approach, I would go for this one instead of the reverse index one. --Naba Kumar (talk) 19:31, 28 May 2011 (UTC)

Re why not to add it to the article: because we need a reliable source that describes this alternative approach. I discussed it eight years ago here but I don't think that counts as a reliable source unless you want to go with the "established expert" clause of WP:SPS (plausible as I have published about other aspects of shortest paths but I'm certainly not going to add it myself). I don't know of published sources that talk about doing it this way. —David Eppstein (talk) 19:51, 28 May 2011 (UTC)

Here's one source which talks about this idea: [2]. They further eliminate space disadvantage you mentioned by using a balanced tree (standard in C++) which does everything heaps can do plus an efficient find operation (if you know key's priority). -- X7q (talk) 20:54, 28 May 2011 (UTC)

@X7q: That's also an interesting approach. However, I see that "find" in the balanced-tree using the priority key could be risky because there can potentially be vertexes with same priority (you want to decrease-key your current vertex, not any vertex with same priority). I believe that's reason why this may not be a reliable choice. -- Naba Kumar (talk) 12:06, 31 May 2011 (UTC)

We use (priority, vertex number) pairs as keys in the tree, not just priorities. And there's at most one key per vertex - decrease-key operation is implemented by removing (previous priority, vertex) and inserting (new priority, vertex). This is why it works correctly. -- X7q (talk) 14:02, 31 May 2011 (UTC)

@David: That approach is so useful for implementers, I would hazard "citation needed" and still mention it. Ideally, it could be described so that it's trivially logical, so as not to require external proof/citation. For example, as long as it is explained that priority of a vertex only reduces and never increases, and that the queue "does not care" about duplicate entries since old priorities are still intact for older entries for it to function correctly, then I think it can survive. It's a tip most people will easily miss (or re-invent) if not mentioned. Let me put this tip in article (with ref. to you, of course) and see if it survives scrutiny :). -- Naba Kumar (talk) 11:41, 31 May 2011 (UTC)

Is it certaint that Dijkstra in general has running time $O(|E|\cdot dk_{Q}+|V|\cdot em_{Q})$ ? If sources are needed I highly recommend taking a look at this book: http://www.cs.berkeley.edu/~vazirani/algorithms/all.pdf (S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, 2006: "Algorithms"). High quality stuff written by world class researchers. Section 4.4 deals with Dijkstra specifically in the case with a priority queue with explicit definition of what is meant thereby. Superpronker (talk) 13:00, 7 June 2011 (UTC)

In fact, in the abovementioned on page 125 (the box: "Which heap is best") it is stated that the running time is given as

|V|\cdot {\mathtt {deletemin}}+(|V|+|E|)\cdot {\mathtt {decreasekey}}

where the running time for decreasekey is the same as for insert key. This becomes important in explaining some of the running times. Please, someone, verify that I have got this correctly and update appropriately if there is a mistake in the article. Superpronker (talk) 14:03, 7 June 2011 (UTC)

Most Common Implementation

the article formerly had an unsourced implication that the most common implementation of Dijkstra uses a Fibonacci heap. I'm pretty sure that's wrong, but I can't find a good source for the most common implementation. — Preceding unsigned comment added by 66.31.200.86 (talk) 06:25, 18 February 2012 (UTC)

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. —Preceding unsigned comment added by 64.134.224.50 (talk) 00:50, 21 March 2011 (UTC)

Reply: Well actually you set the root to 0, so that will be smaller than infinity, then you set its neighbors and so on... —Preceding unsigned comment added by 70.42.29.3 (talk) 20:53, 4 May 2011 (UTC)

Reply: Am I the only one who finds it a little ironic that the pseudo-code clearly has a "goto" in the last line? — Preceding unsigned comment added by 99.118.189.11 (talk) 14:14, 20 March 2012 (UTC)

Finding multiple shortest paths

In order to find all shortest paths between two nodes, I believe that the "if alt < dist[v]:" should be changed to "if alt <= dist[v]:".Glen Koundry (talk) 13:59, 6 November 2012 (UTC)

Syntax higlight

I've modified the pseudocode in my sandbox to make it use syntax highlight. I think the language it resembles the most is Fortran, but maybe is not the case. Do you think that this makes it more understandable? http://en.wikipedia.org/wiki/User:WLoku/sandbox — Preceding unsigned comment added by WLoku (talk • contribs) 14:52, 9 November 2012 (UTC)

I prefer boldfaced keywords over the pale yellowish colour. The automatic syntax highlight isn't correct either (e.g. the "for each" isn't highlighted). —Ruud 23:00, 9 November 2012 (UTC)

Algorithm

Step four of the algorithm is confusing. In its language it states that a visited nodes minimum distance will never be changed. This, is wrong as when the current node its switched a new minimum distance is calculated - keeping the distance that is minimum.

This is seen in the animation, where node 4 changes it value from 22 to 22 from steps 2 to 3.

Additionally, the end condition that 'all nodes' have been visited seems tenous, suppose an infinite undirected graph with two identified points (a,b), this would have infite computational time. The pseudocode on this page seems to address - can we make this less ambiguous? 129.67.95.240 (talk) 13:10, 9 August 2011 (UTC)

It's not wrong: when node 4's distance changes that is the 'tentative distance' mentioned in step 3 changing. At that point node 4 is not the current node, node 3 is. 4 is being checked as a neighbor of the current node at 3.

The all nodes termination is fine, too. Dijkstra's algorithm finds the minimal distance between a particular node and all other nodes in the graph (not a single destination), so it's obviously never going to terminate when run against an infinite graph. You need some variant of Dijkstra (such as A* to handle infinite graphs. - MrOllie (talk) 14:58, 9 August 2011 (UTC)

For me, the confusing steps are 2 and 3. On step 2, you mark all nodes as unvisited and next, on step 3, you add all neighbors of current node to the unvisited set. Firstly, is there a reason for the unvisited-mark when having a visited-mark? Secondly, maybe the unvisited set is also unnecessary (as it just binds useful space), because the nodes belonging to this set are those who have distance less than infinity and are not marked as visited. Vevek (talk) 23:28, 15 August 2011 (UTC)

I would suggest to change line 3 in the code for getting the shortest path to:

1  S := empty sequence
2  u := target
3  while u is defined:
4      insert u at the beginning of S
5      u := previous[u]
6  end while ;

This way, you also get the start node. This is not the case in the current version. Milcke (talk) 17:06, 8 October 2011 (UTC)

So the "unvisited set" is not the set of nodes marked as unvisited? That's very confusing. Also, in step 4 we are told to remove the current node from the "unvisited set." But if the current node is the initial node, it isn't in the "unvisited set". — Preceding unsigned comment added by 66.188.89.180 (talk) 22:11, 4 November 2012 (UTC)

Just implemented the pseudocode for Rosetta Code and found these issues

Action decrease-key v in Q at line 24 should be omitted if Q is a set as stated in line 9. The wp back-tracking pseudocode also misses a final insert of u at the beginning of S that must occur after exiting the while loop. --Paddy (talk) 21:12, 21 December 2012 (UTC)

decrease-key v in Q;

Why is this line here? decrease-key was never explained. — Preceding unsigned comment added by Eliotistic (talk • contribs) 04:37, 15 January 2013 (UTC)

Animation could be slightly improved

I don't understand why an otherwise awesome animation takes a lame shortcut at the end with the "That's all" text. The algorithm doesn't take any such shortcut so it just hurts one's understanding to do this. The animation should highlight node 4 as grey then draw an arrow towards node 5 where it decides that the current value is already the best (so does not update) similar to when node 2 evaluates node 3. Then node 4 should turn red as did the others. Once all nodes are red (except maybe 5 for obvious reasons), it helps to visualize that execution is complete. — Preceding unsigned comment added by 67.183.182.104 (talk) 03:24, 5 February 2013 (UTC)

Animation for the colorblind

Holy cow, is that subtle red-green gradient not a good idea for colorblind people! — Preceding unsigned comment added by 71.92.43.97 (talk) 05:31, 13 January 2014 (UTC)

Wrong anim?

Lnt-size: smaller;" class="autosigned">—Preceding unsigned comment added by 109.162.218.57 (talk) 12:31, 7 April 2011 (UTC)

Read the algorithm, it keeps the minimum distance. 129.67.95.240 (talk) 13:03, 9 August 2011 (UTC)

I think I spotted another error: when an arrow is drawn from node #3 to node #4, a question mark and subsequently " 22 < 11 + 9 " is written above node #4. Shouldn't the inequality sign be the other way? 109.129.178.210 (talk) 06:47, 28 April 2012 (UTC)

The Triangle formed by node 1,3 and 6 has wrong length for the line connecting 1 and 6.For a triangle inequality to hold it can't be (14) larger than other two sides length (9+2). — Preceding unsigned comment added by 67.243.136.10 (talk) 00:40, 15 June 2013 (UTC)

Generally the numbers do not represent geometric length, they represent some kind of cost, for example, it could be the travel time between nodes. The 14 could then represent the fact that a farm track takes 14 mins, while the main road only takes 9 + 2 mins down a side street. --tooto 16:03, 24 July 2013 (UTC) — Preceding unsigned comment added by Tooto (talk • contribs)

Shouldn't the animation end with an identification of the selected path? All it does is flash up "20(4) >= 20(5), That's All". Shouldn't it mark the path from A to B (1, 3, 6, 5)? As it stands now, the animation ends with 4 red circles and no clear indication of what was actually accomplished. Additionally, why are circles marked red then labeled OUT? The OUT is confusing. This indicates to me that the vertex is "out" of the path, which is not the case. It's also inconsistent because vertex #6 is not marked out even though it is colored red. 98.165.197.124 (talk) 18:16, 10 August 2013 (UTC)

This animation is simply terrible. From what I can tell, it's trying to depict the algorithm finding the shortest path between a (1) and b (5), and it comes up with 1,2,3,6,5 with a total length of 28. Clearly, the right answer to that question is 1,3,6,5 with a length of 20. I assume the order of turning vertices red is supposed to be the order of the path. On the other hand, if the algorithm is supposed to generate a shortest path tree, why does the animation not show any branching? King rhoton (talk) 06:21, 2 February 2014 (UTC)

When node 4 is reached from node 3, it shows, 22<11+9. Silly mistake i guess.

This psudo code is hard to understand

There is 'no language' for psudo code, but whatever language this psudo-code is closest to is hard for me (and probably others) to understand. Colon-Equal Sign? What does that mean?

Can someone who understands this Psudo-code break it down further? Make it closer to plain English? Don't assume the reader understands the symbols being used in the psudo code please.

There are many different computer languages out there: C/C++, C#, Lua, Lisp, Visual Basic, Quick Basic, Delphi, and many more. Why should someone who writes code in Visual Basic not be able to understand the algorithm on Wikipedia? Why should they have to learn Lisp to be able to decipher the meaning of "psudo-code" to understand and learn something here? It could take someone years to learn another language, if they even have access to the tools/information to learn that other language.

Psudo-code on Wikipedia should probably be written so that someone who doesn't know any programming languages at all can understand it. After all, programming is math. Why should someone have to understand a specific programming language or shorthand to understand an algorithm? Psudo-code on Wikipedia should be universal, or at least understood in the language the page is written in (English and Math for example).

 — Preceding unsigned comment added by 50.129.81.162 (talk) 14:40, 8 February 2014 (UTC)