Is it possible to find the shortest path and visit all the nodes in a graph by A* algorithm? If yes, how?
$\begingroup$
$\endgroup$
7
-
5$\begingroup$ Possible duplicate of Does the A* algorithm visit every node? $\endgroup$– ryanApr 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.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$– ryanApr 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$– JuhoApr 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 WangApr 2, 2019 at 21:48
|
Show 2 more comments