0
$\begingroup$

Please can someone confirm that my description of the application of Dijkstra's algorithm is correct for this graph?

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

Step   Current Node

                       B        C        D
1      A               1(A)     -        2(A)   
2      B               1(A)     4(B)     2(A)   
3      D               1(A)     3(D)     2(A)   
4      C               1(A)     3(D)     2(A)   

Description:

  1. Tentative distances to B and D determined. C not yet visible.
  2. Shortest distance from previous step taken. No new information on shortest path to B. Tentative distance to C now known. No new information on D.
  3. We choose to backtrack to A, and then move to D because the distance to D (2) is smaller than that to C (4). We update the tentative distance to C because via D it is shorter than via B.
  4. We choose to move to C directly from D because it is shorter (3) than backtracking and going via A (4). Moving to C gives us no new shorter distances. All nodes visited, so end.
$\endgroup$
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Jun 1 '17 at 10:18
  • $\begingroup$ Wouldn't it be wonderful if friends, classmates and teachers, willing and able to help with graph algorithms were plentiful? $\endgroup$ – Ben Jun 1 '17 at 12:42
  • 1
    $\begingroup$ It certainly would. It's unfortunate if you don't have anyone else to ask, but that doesn't make the question a good match for this site. $\endgroup$ – David Richerby Jun 1 '17 at 14:05
1
$\begingroup$

It's more traditional to describe dijkstra with the open and closed sets:

You start with an empty closed set and an open set containing $ \{ (A,0) \}$

You select the node with the lowest cost and remove it from the open set, then you expand the neighbours and add them to the open set $ \{ \{B,1\} \{D,2\} \}$ or update the elements in the open set and Add the selected node to the closed set

step1:
open = $ \{ (B,1, A), (D,2, A) \}$
closed = $\{(A)\}$

step2:
open = $ \{ (C,4, B), (D,2, A) \}$
closed = $\{(A),(B,A)\}$

step3:
open = $ \{ (C,3, D) \}$
closed = $\{(A),(B,A),(D,A)\}$

There is no actual sense of "backtracking" because you are considering all the open nodes in parallel.

Many other search algorithms work in the same way with the only difference in how a node is selected from the open set. Breadth-first takes the oldest node in the set, depth-first takes the youngest, Dijkstra takes the node with the lowest cost, A* takes the node with the lowest cost+heuristic.

$\endgroup$
  • $\begingroup$ What do "open" and "closed" mean in this context? $\endgroup$ – Ben Jun 1 '17 at 11:38
  • $\begingroup$ The open set is all the neighbours that you have touched while expanding nodes without any nodes that you have expanded. The closed set is the set of nodes that are already expanded. $\endgroup$ – ratchet freak Jun 1 '17 at 11:46
  • $\begingroup$ Thank you. And why did you choose the words "open" and "closed". i.e. what is literally "open" and what is literally "closed"? $\endgroup$ – Ben Jun 1 '17 at 12:20
  • 2
    $\begingroup$ @BenAston those are the terms used when I learned the algorithm. Another set of terms for them are "frontier" and "visited" those may be a bit more intuitive. $\endgroup$ – ratchet freak Jun 1 '17 at 12:37
  • 1
    $\begingroup$ @BenAston: Those are just the terms that are used. Note that in the real world it's more common to not have a closed set, and instead have a HasBeenVisisted property on each node $\endgroup$ – BlueRaja - Danny Pflughoeft Jun 1 '17 at 13:55

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.