Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis
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.