How to obtain the path in the "uniform-cost search" algorithm?

Question

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?

Answer 1

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.