How to obtain the path in the "uniform-cost search" algorithm?
37,647
Usually you start with a infinite total cost for every node that hasn't been explored yet. Then you can adjust the algorithm a little bit to save the predecessor:
for each of node's neighbours n
if n is not in explored
if n is not in frontier
frontier.add(n)
set n's predecessor to node
elif n is in frontier with higher cost
replace existing node with n
set n's predecessor to node
Afterwards you can just check the sequence of predecessors, starting at your goal.
Comments
-
Max over 4 years
I have been going through the algorithm of uniform-cost search and even though I am able to understand the whole priority queue procedure I am not able to understand the final stage of the algorithm.
If we look at this graph, after applying the algorithm I will have the minimum distance for each node, but suppose I want to know the path between A to G (just like the example), how will I compute that?