Understanding Dijkstra's algorithms

Question

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?

Answer 1

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

5. Take the first node from OPEN, $n=C$
6. It is not the goal state, $C\neq B$
7. 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).
8. Add $C$ to CLOSED as it has been expanded, CLOSED=$\{A, C\}$

Iteration 3

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

Hope this helps,

Answer 2

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)

Answer 3

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)

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