Uniform-cost Search or Dijkstra's algorithm (Russell Norvig)

As outlined in Russell Norvig Chapter 03: Solving Problems by Searching

Definition

A Search Algorithm that adopts an Uninformed Search Strategy:

When actions have different costs, an obvious choice is to use best-first search where the evalution function is the cost of the path from the root to the current node. This is called Dijkstra’s algorithm by the theoretical computer science community, and uniform-cost search by the AI community. The idea is that while breadth-first search spreads out in waves of uniform depth… uniform-cost search spreads out in waves of uniform path-cost. (p. 95)

Implementation

We implement uniform-cost search as a call to Best-first-search where the evaluation function f(n) is the path cost.

Pseudocode

Properties and Performance

Note that uniform-cost search must use a late goal test, or it risks returning a suboptimal path.

Uniform-cost search is complete and is cost-optimal, because the first solution it finds must have a cost that is at least as low as any other node on the frontier. It considers all paths systematically in order of increasing cost and never gets stuck down a single path (assuming all action costs are \(> \epsilon > 0\), with \(\epsilon\) being a notional minimal bound action cost.

Regarding time and space performance, the complexity is understood in terms of \(\epsilon\) and \(C^*\), the cost of the optimal solution.

The algorithm’s worst-case space and time complexity is: \(O(b^{1+ \left \lfloor{C^* / \epsilon}\right \rfloor})\). This can be much worse than breadth-first search’s \(O(b^d)\), since uniform-cost might explore large trees of low-cost actions before exploring high-cost paths which are more useful. When all action costs are equal then the performance is just \(b^{d+1}\), so similar to breadth-first search.