# Uniform-cost Search Problem

Suppose that we take an initial search problem and we add $c > 0$ to the costs on all edges. Will uniform-cost search return the same answer as in the initial search problem?

Definitions: Uniform-cost search is also known as lowest cost first. Initial search problem can be any graph with a start and a goal state. You just apply the uniform cost search algorithm on the graph.

• What is an initial search problem? What is uniform-cost search? Where do the edges come in? – Yuval Filmus Jan 29 '13 at 2:55
• @Yuval: Uniform-cost search is also known as lowest cost first. Initial search problem can be any graph with a start and a goal state. You just apply the algorithm on the graph. – Dave Jan 29 '13 at 3:27

The shortest path may indeed change. This is not because of some property of the uniform cost search, but rather, the property of the graph itself. Note that adding a constant positive cost to each edge affects more severely the paths with more edges. Here is an example, where the shortest path has cost $5$: Adding a cost of $1$ to each edge changes the shortest path in the graph as: The original shortest path has a new cost of $10$, whereas the other path has a cost of only $9$. Therefore, any optimal shortest path algorithm, such as Dijkstra's or uniform cost search, will find a different shortest path.

The shortest path will not change if it also has the least number of paths among all paths from source to destination. If the shortest distance is $d_{min}$ and $k_1$ edges, and there is some other path with distance $d_{min} + \Delta$ with $k_2$ edges ($k_2 < k_1$), it can be shown that adding any $c > \frac{\Delta}{k_1 - k_2}$ to all the edges will change the shortest path, and therefore your result.

Scaling the edges by a constant positive factor (multiplying all edges by $c>0$) will not change the shortest path.

The answer is no, solutions may differ. If suppose your optimal solution in a graph was $s \in \mathbb{R}$ for a path of length $\ell$. If you add $c > 0$ to all edges, this new path will get cost $s + \ell c$.

If there is a different (worse) solution of cost $s - \epsilon$, where $0 < \epsilon < c$, and with a path length $< \ell$, you will now get an alternate solution of cost $\leq s + \epsilon + (\ell - 1) c$ which is less then the optimal solution before adding $c$ to every edge.