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

Question

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.

These statements seem contradictory.  
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.

Answer 1

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.