# 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.

-

2
What is an initial search problem? What is uniform-cost search? Where do the edges come in? – Yuval Filmus Jan 29 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 at 3:27

## 2 Answers

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 21, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9308444857597351, "perplexity_flag": "head"}