COMP1927 - Dijkstra (Shortest Path)

Djikstra's shortest path algorithm is essentially A* but with a heuristic of 0 (so all calculations are done on path length/weight).

At each step all children nodes (or edges out from a vertex or etc) are inserted on to the priority queue with their edge weight added to their parents path length. As such nodes are selected until the goal state is found.

Classification

  • Complete: Yes, if the branching factor is finite and the step cost (cost of moving between states) is >= epsilon (not sure what this is), and epsilon > 0
  • Time-Complexity: $O(b^{\frac{c}{\epsilon}})$
    • where c is the cost of optimal solution, and we assume every action costs at least epsilon. Equivalent to ElogV.
  • Space-Complexity: $O(b^{\frac{c}{\epsilon}})$ (= $O(b^d)$ if all the steps are equal cost.
  • Optimality: Yes (it always finds the least-cost solution).