Uniform Cost Search

        def uniform_cost_search(start):
            cost_to_get_to_node = {}
            frontier = PriorityQueue() // Higher Priority equals Lower Cost
            expanded_nodes = Set()

            cost_to_get_to_node[start] = 0
            frontier.push((start, 0))
            expanded_nodes.add(start)

            while front.has_elements():
                u = frontier.pop()

                if is_goal(u):
                    return path(u)

                for v in u.successors:
                    if v not in expanded_nodes:
                        if v in frontier:
                            # if we already have it in the frontier, but we found a cheaper way to get there, update the cost to get here.
                            cost_to_get_to_node[v] = min(cost_to_get_to_node[v], cost_to_get_to_node[u] + u.action_cost(v))
                        else:
                            frontier.push(v)
                            cost_to_get_to_node[v] = cost_to_get_to_node[u] + u.action_cost(v))

            return Failure

In general UCS is not complete, because given an infinite number of zero-weight edges deviating away from the goal state, then UCS will follow this path forever and never find the goal. On the other hand, if there exists some ϵ > 0 such that every edge has at least this weight, then UCS will find the minimum cost solution, this is because it explores nodes in the search space in non-decreasing order of cost so it must find a minimum cost path to a goal before finding any higher cost paths leading to a goal.

UCS Example Graph
Show the history of the frontier and what node is selected in a table for the following graph, where UCS is called without the cycle checking.
pathfrontierabout to expand
(S, 0)S
S(SP, 1), (SD, 3), (SE, 9)(SP, 1)
(SP, 1)(SD, 3), (SE, 9), (SPQ, 16)(SD, 3)
(SD, 3)(SE, 9), (SPQ, 16), (SDE, 5)(SDE, 5)
(SDE, 5)(SE, 9), (SPQ, 16), (SDEH, 6)(SDEH, 6)
(SDEH, 6)(SE, 9), (SPQ, 16), (SDEHQ, 10)(SE, 6)
(SE, 9)(SPQ, 16), (SDEHQ, 10), (SEH, 10)(SEH, 10)
(SEH, 10)(SPQ, 16), (SDEHQ, 10), (SEHQ, 14)(SDEHQ, 10)
(SDEHQ, 10)(SPQ, 16), (SEHQ, 14), (SDEHQG, 11)(SDEHQG, 11)
(SDEHQG, 11)(SPQ, 16), (SEHQ, 14)
Later Expansion means Higher Cost
Suppose that node a is expanded after node b then c ( b ) ≤ c ( a )
Strictly Less Cost Implies Earlier Expansion Time
Let v be a node expanded by UCS, then for any node x ∈ V such that c ( x ) < c ( v ) , then x will be expanded before v will be.
UCS Produces Minimal Cost Paths
Let p be the first path that UCS produces that leads to some node x , then p is a minimal cost path to x , so long as all costs are lower bounded by some ϵ ∈ R > 0 .

Note that if we don't have the lower bound assumption, then there could exist some negative edge weights meaning that there is potential for a high cost path, to then eventually become a very low cost before getting to x which would mean that UCS would find some other higher cost path to x before making it over the "hump" of the other path to x with lower cost. This is similar to escaping a local minimum.

Suppose that p is the first path that UCS produces that leads to some node x , then assume for the sake of contradiction that this path is not cost optimal, therefore there exists some other path p ∗ that has lower cost, but then p ∗ would be a path leading to x that gets explored before p but p was the first one, so this is a contradiction, therefore p is the minimal cost path to x .

UCS Runtime
Suppose that we have a directed graph with maximum branching factor b with edge weights such that there exists some ϵ > 0 such that every edge weight is at least this amount. If s , g are two connected in the graph and let C ∗ be the minimal cost a path can have that starts from s and goes to g , then the runtime and space complexity of calling UCS on s is given by O ( b ⌊ C ∗ ϵ ⌋ + 1 )

By the above lemmas we know that UCS will expand all nodes with a cost less than C ∗ and potentially (in the worst case) all nodes with cost equal to C ∗ . If we know that the minimal cost to get from s to g is C ∗ , and each edge has weight at least ϵ , then the maximal number of edges in this path is given by d = ⌊ C ∗ ϵ ⌋ , to understand why this is true, suppose that C ∗ = 9 and ϵ = 5 , ⌊ C ∗ ϵ ⌋ = ⌊ 9 5 ⌋ = 1 , but clearly we're going to need at least two edges to reach our goal, because if we had just one, we would have cost 5 , but this path couldn't reach g because any path that reaches g must have cost at least 9 , this is why the equation is ⌊ C ∗ ϵ ⌋ + 1 , which our our specific case would be equal to 2 which makes sense.

If we isolate our attention to the subtree with depth d , then in the worst case every edge inside this subtree has weight ϵ , and therefore every node in a higher level in the tree has a lower cost and must be explored before we explore node g .

Everything at layer d has the same cost of ϵ ⋅ d . Then bringing our attention back to the whole tree, any node that is outside of this subtree will have cost greater than ϵ ⋅ d , and thus none of them will be expanded by U C S while trying to find g .

Let's now calculate how many nodes UCS actually has to expand Since UCS explores nodes with a lower path cost first, then the entire subtree of depth d − 1 will be explored before g , then at depth d in the worst case, every other node is expanded before g , therefore in total we have to explore b 0 + b 1 + … b d − 1 = b d + 1 − 1 b − 1 − 1 nodes, therefore our runtime is given by O ( b d ) = O ( b C ∗ ϵ + 1 )