# Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis

Our professor took three statements from various textbooks that seem to be a little contradictory regarding the complexity analysis of Dijkstra’s algorithm as well as the lowest-cost-first or best first algorithm.

Edit: I've discovered a related question which can be referenced here: https://stackoverflow.com/questions/10374357/why-use-dijkstras-algorithm-instead-of-best-cheapest-first-search

The statements are as follows:

•   “…lowest-cost-first search is typically
exponential in both space and time.  It
generates all paths from the start that have
a cost less than the cost of a solution.”
(Poole, 2nd ed., Section 3.5.4, last
sentence)

•   Dijkstra’s algorithm runs in time O(V^2)
(Cormen, et. al., Ch. 24)

•   Lowest-cost-first search is Dijkstra’s
algorithm where you terminate the search
after you have found the shortest distance to
the goal node.

How do you resolve the contradictions?


I'm a bit confused about how to approach this question.

From what I've gathered, the answer may have to do with the fact that lowest-cost-first search is said to be an uninformed search strategy whereas, Dijkstra's is said to be an informed search strategy but I don't fully understand the implication.

The first statement confuses me the most, the part that says that:

"It (lowest cost first) generates all paths
from the start that have a cost less than the
cost of a solution"


My guess is that this statement refers to bounded arc costs which the same text further elaborates on by stating:

If the costs of the arcs are all greater than
a positive constant (bounded arc costs) and
the branching factor is finite, the lowest-
cost-first search is guaranteed to find an
optimal solution – a solution with lowest
path cost


and

The bounded arc cost is used to guarantee the
lowest-cost search will find a solution, when
one exists, in graphs with finite branching
factor. Without such a bound there can be
infinite paths with a finite cost.


However this is difficult for me to understand as I am still very much a novice student. If anyone could help explain this I would be eternally grateful, thank you.

Imagine you're playing a game, and are currently at state $$S_{0}$$. In order to win, you must reach the state $$S_{finish}$$.

In every turn, you can do one of $$c$$ moves. Your goal is to reach $$S_{finish}$$ in as little moves as possible; in other words, every move has a cost $$1$$.

To find the optimal path $$P = \{S_{0}, S_1, S_2 \dots S_{finish}\}$$, would be finding the set of moves $$c_1 \dots c_n$$ so that $$P$$ is minimum.

So what would a lower cost first algorithm do? the same thing a $$BFS$$ would do; in each turn $$i$$, search $$S_i^1...S_i^c$$ possible states that can be reached from the previous state $$S_{i-1}$$.

so, searching $$n$$ times, how many moves have you effectively searched?

$$1$$ in turn 1

$$c + 1$$ in turn 2

$$c*c + c+1$$ in turn 3

$$=\sum_{i=0}^{n-1} c^i$$ in turn $$n$$, which is exponential in $$n$$.

But its also exponential in terms of space. To search all the next states $$S_{i+1}$$, you must keep all your current states $$S_i$$ in your memory.

How many states $$S_i$$ are there? $$c^i$$ as shown above.

When your professor mentioned Dijkstra is polynomial in $$V$$, he meant on input size that is $$V,E=n, O(n^2)$$ respectively. However, when searching the optimal path to some wanted state, like in chess, the number of states (or $$V$$ essentially, if we suppose a state is a vertex), grows exponentially.