# Résolution de problèmes algorithmiques

Given a grid with a source cell, a destination cell and obstacle cells, find the shortest path from the source to destination, where every direction change along the path costs 1.

Say the grid has dimensions n times n.

## A simple BFS traversal in time $O(n^3)$

Consider a graph, where every vertex is a cell of the grid, and there is an edge between two cells of the same column or the same row if they are not separated by an obstacle. Now the problem consists in finding a shortest path in this unweighted graph, and this can be done using a BFS traversal of the graph. There are $O(n^2)$ vertices and $O(n)$ edges, which leads to the claimed complexity.

## A better analysis shows time is $O(n^2)$ in fact

When you visit a cell u at distance dist[u] from the source, then you will explore all neighbors: For each of the 8 directions you will explore the cells in that direction at increasing distance from u, and stop once you reached a cell v that is either on the boundary of the grid, or has already been visited. But you can also stop if dist[v] equals dist[u]. Because this means that when later you visit vertex v, anyway you will explore the vertices which are beyond v in the u-v direction.

As a result you will look at a cell v at most 8 times, once for each direction. Hence the algorithm runs in linear time.

## Improvement through Algorithm A* ?

The algorithm A* is an improvement of the standard Dijkstra shortest path algorithm. All we need is a lower bound on the shortest path to the destination. We model the problem as follows. The queen always stands in some grid cell facing some direction. She can either walk for free one step in her direction or at the cost of 1 unit walk one step in another direction. Suppose that the queen stands in position (0,0) and the destination cell is (x,y). For the lower bound assume that the grid has infinite dimensions and is free of obstacles. Then the queen could reach the destination in 0, 1, or 2 steps, depending on the directions she is currently facing. The cost can be determined through a careful case analysis.

Experiments show that this solution is slower than the BFS described above.

• See here for another explanation by Hasan Zobayer.