This quiz is taken from the problem set 8 for the MIT course 6.046
"Introduction to Algorithms", by C.E. Leiserson and E. Demaine.

Consider the paths that connects two points, S and T, in a maze, with no left or U turn. Find an efficient algorithm that, given a m X n map of the maze, finds the path with the minimum number of right turns, or reports that such a path does not exists. Ties between paths with the same number of right turns should be broken by taking the shortest path.

Thus the weight of a path is given by two integers: the number of right turns, and the total straight line distance. When a step is added to a path its weight increase as

(R,D) -> (R+1,D) if the step is a right turn (R,D) -> (R,D+1) otherwise

One solution is to create a graph representation of the problem
and to use the graph shortest path algorithm (Dijkstra) to find the
optimal path. Each edge (u,v) in the graph has two weights,
w_{r}(u,v)=1 if the edge represents a right turn, and
w_{s}(u,v)=1 if the edge represents a straight movement.
For each cell in the maze there are four nodes, N, S, W, and E, corresponding
to the possible directions the cell is entered. The edges from a
node are the directions the path can leave the cell. Only straight
line or right turn edges are possible.

The edge weight are a pair of positive numbers W=(w_{r},w_{s}).
They are ordered by W<W' iff w_{r}<w'_{r} or
w_{r}=w'_{r} and w_{s}<w'_{s}.
We can therefore apply Dijkstra algorithm.
The graph has O(mn) nodes. Since Dijkstra algorithm runs in O(V lg(V) + E)
time, this algorithm runs in O(mn lg(mn)) time.

"If we don't care about breaking ties by straight-line distance, and we want just a path with minimum number of right turns, then it is possible to optimize the priority queue for Dijkstra's algorithm to support priority queue operations in O(1) time. This reduces the runtime of the algorithm to O(mn)."

"We conjecture that there exists an O(mn) algorithm to solve this problem when we do break ties by straight-line distance"

Consider the following algorithm.
It uses a mXn array to store the four minimum weights for path exiting
the cell in the four directions N, S, W, and E. They are all initialized to
infinity. If a cell cannot be exited in a direction the corresponding
weight will always remain infinity. Then construct a FIFO list of
triplets (cell, from, weight), where cell is a cell in the maze,
from is the neighbor cell before it on an optimal path, and weight is the
weight of the optimal path from S to the cell.
The list is initialized by putting (S, nil, 0) on it. While the list is
not empty, pop an item and add the neighbors that, if reached
from the cell, decrease its weight for exiting in the corresponding
direction. For example if (C, F, w) can be followed by (N, C, w') to the
South, if w'=w+w(move) if less than w_{south}(C), add (N, C, w') to
the list and update w_{south}(C) = w'.

OptimalPath( S, T ) reachable <- false LIST list for C <- 1 to mn do Weight[C,North] = inf; Weight[C,South] = inf; Weight[C,West] = inf; Weight[C,East] = inf; list.Push( S, nil, 0 ) cursor <- list.start while cursor != list.end ( C, F, w ) <- cursor if C = T then reachable <- true OutputPath(C) else do for K in {North,South,West,East} do N = C + K w0 <- Move( F, C, N ) // inf if cannot make the move if w+w0 < Weight[C,K] then Weight[C,K] <- w+w0 list.Push( N, C, w+w0 ) cursor <- cursor.next if ! reachable then output "Target not reachable" OutputPath(C) while C != nil do output(C,F) // path is written backwards

What is computational complexity of this algorithm? Probably it is no better that Dijkstra's algorithm. However, by suitably structuring the list of moves one can achieve O(mn) complexity. The idea is to have a two-level priority queue: an item on the top level collects the moves with the same number of right turns. These are organized in a priority-queue by the number of straight steps.

R=0 R=1 S=0 S=1 S=2 ... S=1 S=2 ... where R=0,S=0: {m | w(m)=(0.0)} R=0,S=1: {m | w(m)=(0.1)} ... R=1,S=1: {m | w(m)=(1.1)} ...The list is scanned until the target is reached, or no move are available. Can you prove it?

Marco Corvi - 2009