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
    Commented Apr 2, 2019 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.
    Commented Apr 2, 2019 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
    Commented Apr 2, 2019 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
    Commented Apr 2, 2019 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
    Commented Apr 2, 2019 at 21:48


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.