Who knows the Sedgewick-Vitter algorithm?

Question

I have to implement Dijkstra and Sedgwick-Witter algorithms without using the Fibonacci bunch. Information about Dijkstra is complete internet, but I could not find pseudo-code or examples of the Sedgewick-Vitter algorithm. I just found that there is some information in McHugh, the book "Theory of Algorithmic Diagrams", but I could not find a free pdf file. So maybe someone knows this algorithm and can share information, pseudo-code, links?

Hooray!

Answer 1

Assume a graph with Euclidean distances. The source is s, and the destination is t.

As you know, Dijkstra's algorithm visits the vertices x in order of non-decreasing distance (s, x).

Algorithm A * visits vertices x in order of non-decreasing distance (s, x) + h (x). The function h must be a valid heuristic, which in this case means that h (x) ≤ distance (x, t). Consider the various options for h.

• h (x) = 0. This forces A * to behave like a Dijkstra.

• h (x) = distance (x, t). This is the best allowable heuristic. A * will visit only those vertices with distance (s, x) + distance (x, t) = distance (s, t), i.e. Those vertices are on the shortest path from s to t. Unfortunately, this choice of h is expensive to calculate.

• h (x) = || x - t ||. The direct distance is calculated in time O (1) and is always the lower boundary of the distance.

The latter heuristic works well when there is a reasonable direct shot from s to t, but as heaps roll around, A * will visit many peaks that are “off the road”.

Sedgewick-Vitter rotates it to 11 using h (x) = a || x - t || for a> 1. Heuristic is unacceptable, therefore, we cannot find the shortest path, but, by punishing the early workarounds, he hopes to trim the search space without reducing the quality of the solution too much.