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