algorithm – Uniform Cost Search in Python

algorithm – Uniform Cost Search in Python

Usually for searches, I tend to keep the path to a node part of the queue. This is not really memory efficient, but cheaper to implement.

If you want the parent map, remember that it is only safe to update the parent map when the child is on top of the queue. Only then has the algorithm determined the shortest path to the current node.

def ucs(G, v):
    visited = set()                  # set of visited nodes
    q = queue.PriorityQueue()        # we store vertices in the (priority) queue as tuples 
                                     # (f, n, path), with
                                     # f: the cumulative cost,
                                     # n: the current node,
                                     # path: the path that led to the expansion of the current node
    q.put((0, v, [v]))               # add the starting node, this has zero *cumulative* cost 
                                     # and its path contains only itself.

    while not q.empty():             # while the queue is nonempty
        f, current_node, path = q.get()
        visited.add(current_node)    # mark node visited on expansion,
                                     # only now we know we are on the cheapest path to
                                     # the current node.

        if current_node.is_goal:     # if the current node is a goal
            return path              # return its path
        else:
            for edge in in current_node.out_edges:
                child = edge.to()
                if child not in visited:
                    q.put((current_node_priority + edge.weight, child, path + [child]))

Note: I havent really tested this, so feel free to comment, if it doesnt work right away.

A simple check before expanding the node can save you duplicate visits.

while not q.empty():             # while the queue is nonempty
    f, current_node, path = q.get()
    if current_node not in visited: # check to avoid duplicate expansions
       visited.add(current_node)    # mark node visited on expansion,
                                    # only now we know we are on the cheapest path to
                                    # the current node.
       if current_node.is_goal:     # if the current node is a goal
          return path               # return its path
       ...

algorithm – Uniform Cost Search in Python

Leave a Reply

Your email address will not be published. Required fields are marked *