Menu
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?
916
Conclusion. Uniform Cost Search is a type of uninformed search algorithm and an optimal solution to find the path from root node to destination node with the lowest cumulative cost in a weighted search space where each node has a different cost of traversal.
uniform cost searches for shortest paths in terms of cost from the root node to a goal node. Uniform Cost Search is Dijkstra's Algorithm which is focused on finding a single shortest path to a single finishing point rather than the shortest path to every point.
Conclusion. This article introduced both Dijkstra's algorithm and the Uniform-Cost Search algorithm. Both algorithms are finding the shortest path with the least cost i.e. Dijkstra's algorithm: finds the shortest path from one node to every other node in the graph, UCS: finds the shortest path between 2 nodes.
Uniform-cost search is an uninformed search algorithm that uses the lowest cumulative cost to find a path from the source to the destination. Nodes are expanded, starting from the root, according to the minimum cumulative cost. The uniform-cost search is then implemented using a Priority Queue.
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.
87
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
