1
$\begingroup$

As far as I understand, Dijkstra's algorithm always picks the nearest neighbour.

But how does it work for the following graph?

    2
A-------B
 \     /
1 \   / 3
    C

var result = dijkstra(fromA, toB);

Step1: A->C is the shorter
Step2: C->B is the shorter
Answer: 1 + 3 === 4 // This is clearly wrong

What am I missing?

$\endgroup$
  • 3
    $\begingroup$ Try running the pseudocode of Dijkstra's algorithm on Wikipedia, and you'll see what you're missing. $\endgroup$ – Yuval Filmus Apr 28 '16 at 9:46
  • $\begingroup$ Presumably it is this idea of tentative distances that I am missing. Please can you clarify this aspect of the algorithm? $\endgroup$ – Ben Apr 28 '16 at 9:49
  • 2
    $\begingroup$ Dijkstra's algorithm is not really one algorithm; it's an algorithmic idea. There are several different implementations of this idea. If you don't spell out what Dijkstra's algorithm means to you, this question would be hard to answer. If you do spell it out, you might as well program it and trace its execution. $\endgroup$ – Yuval Filmus Apr 28 '16 at 9:50
  • $\begingroup$ Dijkstra is not an algorithm??? Dijkstra certainly never used the word "algorithm" in his paper "A note on two problems in connexion with graphs", Numerische Mathematik, pp. 269--271, 1959. But I could not believe it is not an algorithm: it has well defined inputs and outputs and there is a simple implementation of it. Yuval, you're killing my whole field of research! :) :) Cheers, $\endgroup$ – Carlos Linares López Apr 29 '16 at 8:23
  • 1
    $\begingroup$ !! There is no need a ton of documents, explanations or something else. Just watch the video visitors of the question. !! $\endgroup$ – itsnotmyrealname May 28 '17 at 21:17
4
$\begingroup$

Dijkstra works as follows:

  1. Take the first node from OPEN. Let $n$ denote such node. OPEN contains all nodes generated in ascending order of $g(n)$, where $g(n)$ is defined as $\sum\limits_{i=1}^{n-1} c(v_i, v_{i+1})$, and $c(v_i, v_{i+1})$ is the cost of the edge from $v_i$ to $v_{i+1}$. In other words, $g(n)$ is the sum of the edge costs in the path from the start state to node $n$.
  2. If $n$ is the goal state, then halt. The optimal solution is the path from $s$ to $n$.
  3. If $n$ is not the goal state, then verify whether it has been expanded before or not. Another list, called CLOSED contains those nodes already expanded. If $n$ is found in CLOSED, then go to 1. Otherwise, expand $n$ generating its successors. Evaluate $g(n')$ for each descendant $n'$ and add them to OPEN.
  4. Remember you expanded $n$, so add it to another list called CLOSED. Go to 1.

Initially, OPEN=$\{s\}$ where $s$ is the start state and CLOSED=$\varnothing$ as you have expanded no node yet.

From your execution trace, it seems to me that you overlooked step 2, ie., Dijkstra stops when it is about to expand the goal state, and not when it is generated. As a matter of fact, you may generate the goal state an arbitrary number of times, but condition 2 is met only once.

Hence, in your specific case, Dijkstra works as follows:

Iteration #1 OPEN=$\{A\}$ and CLOSED=$\varnothing$

  1. Take the first node from OPEN, $n=A$
  2. It is not the goal state $A\neq B$
  3. It does not appear in CLOSED, ie., it has not been expanded before. So that its descendants are generated: $C$ with a cost equal to 1 and $B$ with a cost equal to 2. They are now added to OPEN in ascending order of $g(n)$ so that OPEN=$\{C, B\}$
  4. Add $A$ to CLOSED as it has been expanded, CLOSED=$\{A\}$

Iteration #2

  1. Take the first node from OPEN, $n=C$
  2. It is not the goal state, $C\neq B$
  3. It does not appear in CLOSED, ie., it has not been expanded before. So that its descendants are generated: $B$ (its parent $A$ is easily removed as it is clearly its parent, but you can try to generate it as well and you'll see Dijkstra works smoothly the same). $B$ has now a $g$-value equal to 4 as it has been generated through the path $\langle A, C, B\rangle$. Hence, OPEN contains now $B$ twice: OPEN=$\{B, B\}$, the first one with a value equal to 2 (generated in the first iteration) and the second with a value equal to 4 (generated in this iteration).
  4. Add $C$ to CLOSED as it has been expanded, CLOSED=$\{A, C\}$

Iteration 3

  1. Take the first node from OPEN, $n=B$ (with a cost equal to 2).
  2. It is the goal state. Halt with the path $\langle A, B\rangle$

Hope this helps,

$\endgroup$
3
$\begingroup$

According to me every node must be visited as per the given representation given. So the answer would be 2 because firstly it goes from A to C and then to be B so cost would be high.(directly from A to B is efficient)

$\endgroup$
1
$\begingroup$

I suggest you visit the following link, it really helped me at understanding algorithms, including Dijkstras algorithm. Dijkstra Visualisation

As far as I understand, the algorithm says that at each new node visited, the distances from the source node to its adjacent nodes is updated, in case it is a shorter path.(Initially for all nodes except the adjacent nodes of source node, shortest path is infinity)

enter image description here

Here is an incomplete execution of the algorithm. Eventually, when we reached D, we updated the cost/path to B.

Hence, unless your graph is directed, your implementation may be incorrect.You should have recorded the path to B in your graph from A

You can also see the video that the picture is taken -> Dijkstra's Algorithm: Another example

Cheers

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.