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

Marco Corvi - 2009