Is it possible to find the shortest path and visit all the nodes in a graph by A* algorithm? If yes, how?

  • 5
    $\begingroup$ Possible duplicate of Does the A* algorithm visit every node? $\endgroup$ – ryan Apr 2 '19 at 18:30
  • $\begingroup$ @ryan This question is not a duplicate of that question. Closely related? yes. Duplicate? not. That question is about whether an A* algorithm is supposed to visit every node (so that it will not miss the shortest path). This question is about how to define an A* algorithm so that it will visit all nodes. $\endgroup$ – John L. Apr 2 '19 at 19:34
  • 1
    $\begingroup$ @Apass.Jack I see your point. A* is a defined algorithm, I'm not sure what it means to "define an A* algorithm". Do you mean to define a heuristic function such that these conditions hold? $\endgroup$ – ryan Apr 2 '19 at 20:16
  • 1
    $\begingroup$ If you just want an example of where this happens, suppose $s$ and $t$ are connected by a unique path and that there are no vertices outside this path in the whole graph. $\endgroup$ – Juho Apr 2 '19 at 21:39
  • 1
    $\begingroup$ To get your algorithm to visit all the nodes, you could just not terminate the algorithm when the shortest path from u to v is found. Then, you will find the shortest path from u to each node as well. $\endgroup$ – Kevin Wang Apr 2 '19 at 21:48

Your Answer

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

Browse other questions tagged or ask your own question.