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

Uniform Cost Search is an algorithm best known for its searching techniques as it does not involve the usage of heuristics. It is capable of solving any general graph for its optimal cost. Uniform Cost Search as it sounds searches in branches that are more or less the same in cost.

The algorithm uses the priority queue. This can be shown as follows: 

1. Insert the root into the queue
2. While the queue is not empty
3. Dequeue the maximum priority element from the queue
4. (If the priorities are same in the queue then the alphabetically smaller path is chosen)
5. If the path ends at the goal state then print the path and exit
6. Else 
7. Insert all the children of the dequeued element, with the cumulative costs as a priority

If you are looking to learn more about a uniform-cost search algorithm then you visit this Java Tutorial. Also, if you are appearing for job profiles of Java Developer or Java Expert then you can prepare for the interviews on Java Interview Questions.