4.1.3. Uniform Cost Search

Uniform Cost Search

Uniform Cost Search (UCS) is a graph traversal algorithm that expands the lowest-cost frontier node first, implemented with a priority queue ordered ascending by the path cost function $g(n)$, which represents the cumulative cost from the start state to node $n$.

It is complete and optimal as long as all edge costs are nonnegative, ensuring the discovery of the lowest-cost path to the goal. Its runtime is $O(b^{C^{\ast }/ϵ})$, where $C^{\ast }$ is the cost of the optimal solution and $ϵ$ is the minimum edge cost, with space complexity of the same order.

\usetikzlibrary{trees,animations}
 
\begin{document}
\begin{tikzpicture}[
 level 1/.style={sibling distance=28mm, level distance=14mm},
 level 2/.style={sibling distance=18mm, level distance=14mm},
 nodestyle/.style={draw, circle, inner sep=2pt, minimum size=6mm}
]
 
% --- Static tree (always visible) ---
\node[nodestyle, name=A] {A}
 child { node[nodestyle, name=B] {B}
   child { node[nodestyle, name=D] {D} }
   child { node[nodestyle, name=E] {E} }
 }
 child { node[nodestyle, name=C] {C}
   child { node[nodestyle, name=F] {F} }
 };
 
% Edge cost labels (kept above to avoid node-label overlap)
\path (A) -- node[pos=.5, above left] {2} (B);
\path (A) -- node[pos=.5, above right] {1} (C);
\path (B) -- node[pos=.5, above left] {1} (D);
\path (B) -- node[pos=.5, above right] {20} (E);
\path (C) -- node[pos=.5, right] {5} (F);
 
% Node highlight radius
\def\rvis{4mm}
 
% ---- Label helpers (formatted and positioned to avoid edges) ----
\newcommand{\gbelow}[2]{\node[anchor=north, yshift=-8pt] at (#1.south) {$g(#1)=#2$};}
\newcommand{\gleft}[2]{\node[anchor=east,  xshift=-6pt, yshift=-2pt] at (#1.west)  {$g(#1)=#2$};}
\newcommand{\gright}[2]{\node[anchor=west,  xshift= 6pt, yshift=-2pt] at (#1.east)  {$g(#1)=#2$};}
 
% --- Step 0: A (g=0) ---
\begin{scope}[animate = {myself:: = {:visible = {0s="true", 1s="false", 8s="false", repeats}}}]
 \fill[teal, opacity=.35] (A) circle (\rvis);
 \gbelow{A}{0}
\end{scope}
 
% --- Step 1: C (g=1) ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 1s="true", 2s="false", 8s="false", repeats}}}]
 \fill[orange, opacity=.25] (A) circle (\rvis);
 \draw[orange, opacity=.7, line width=1pt] (A) -- (C);
 \fill[teal, opacity=.35] (C) circle (\rvis);
 
 % current node label (below)
 \gright{C}{1}
\end{scope}
 
% --- Step 2: B (g=2) ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 2s="true", 3s="false", 8s="false", repeats}}}]
 \foreach \n in {A,C} { \fill[orange, opacity=.25] (\n) circle (\rvis); }
 \draw[orange, opacity=.7, line width=1pt] (A) -- (B);
 \fill[teal, opacity=.35] (B) circle (\rvis);
 
 % current node label (below)
 \gleft{B}{2}
\end{scope}
 
% --- Step 3: D (g=3) ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 3s="true", 4s="false", 8s="false", repeats}}}]
 \foreach \n in {A,C,B} { \fill[orange, opacity=.25] (\n) circle (\rvis); }
 \draw[orange, opacity=.7, line width=1pt] (B) -- (D);
 \fill[teal, opacity=.35] (D) circle (\rvis);
 
 % current node label (below)
 \gbelow{D}{3}
\end{scope}
 
% --- Step 4: F (g=6) ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 4s="true", 5s="false", 8s="false", repeats}}}]
 \foreach \n in {A,C,B,D} { \fill[orange, opacity=.25] (\n) circle (\rvis); }
 \draw[orange, opacity=.7, line width=1pt] (C) -- (F);
 \fill[teal, opacity=.35] (F) circle (\rvis);
 
 % current node label (below)
 \gbelow{F}{6}
\end{scope}
 
% --- Step 5: E (g=22) ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 5s="true", 6s="false", 8s="false", repeats}}}]
 \foreach \n in {A,C,B,D,F} { \fill[orange, opacity=.25] (\n) circle (\rvis); }
 \draw[orange, opacity=.7, line width=1pt] (B) -- (E);
 \fill[teal, opacity=.35] (E) circle (\rvis);
 
 % current node label (below)
 \gbelow{E}{22}
\end{scope}
 
% --- Step 6: Done (all expanded, place at side positions) ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 6s="true", 8s="false", repeats}}}]
 \foreach \n in {A,B,C,D,E,F} { \fill[orange, opacity=.25] (\n) circle (\rvis); }
 \draw[orange, opacity=.7, line width=1pt] (A) -- (B);
 \draw[orange, opacity=.7, line width=1pt] (A) -- (C);
 \draw[orange, opacity=.7, line width=1pt] (B) -- (D);
 \draw[orange, opacity=.7, line width=1pt] (B) -- (E);
 \draw[orange, opacity=.7, line width=1pt] (C) -- (F);
\end{scope}
 
\end{tikzpicture}
\end{document}

Proof

We now prove the time and space complexity of UCS.

• Time Complexity. The longest possible path with cost $\le C^{\ast }$ has depth at most $C^{\ast }/ϵ$, since each edge cost is $\ge ϵ$. Therefore, the number of expandable UCS nodes is bounded by $O(b^{C^{\ast }/ϵ})$, such that the algorithm explores $1+b+b^2+\dots +b^{C^{\ast }/ϵ}=\frac{b^{C^{\ast }/ϵ+1}-1}{b-1}$. This is a very weak bound.
• Space Complexity. UCS stores the entire frontier of nodes with path cost $\le C^{\ast }$, which is maximized around the bottom level $C^{\ast }/ϵ$, such that the number of nodes saved is $b^{C^{\ast }/ϵ}+b^{C^{\ast }/ϵ+1}$. As such, the space complexity is asymptotically $O(b^{C^{\ast }/ϵ})$.