[Solved]: Shortest path from starting cell to all cells in the grid

Problem Detail: 

I found an algorithm for finding the shortest path on grid between selected cell, to all cells on the grid, with $O(KN)$ where $K$ is the number of neighbor cells and $N$ is the number of cells.

How ever if that's true than it's better than A*, Floyd–Warshall and many others. So I probably mistaking some thing. Can you point me what.

Here is a pseudo code for my algorithm, the idea is to calculate simultaneously to all the directions.

The algorithm starts with the call to filter method

class MapFilter {     declare cellsMap, array of numbers with two dimensions, that represent a grid     declare stack, a stack of MapFilter     declare count of type number     read input to map, array of Cells with two dimensions, that represent a grid     read input to x ,y those are coordinates of starting node      function filter(){         initialize cellsMap with empty grid, all values are 0         set count = 1         set cellsMap[x][y] = 1;         execute();         while(stack is not empty){             read length of the stack to length             iterate over i from 0 to length{                 remove first element from stack and store it in mapFilter, instance of MapFilter                 mapFilter.execute()             }         }     }      function execute()     {         populate(x + 1, y);         populate(x - 1, y);         populate(x, y + 1);         populate(x, y - 1);     }      function populate(x, y)     {         // Testing if the x,y cell is blocked by some way         if( not isInMapRange(x,y) or             cellsMap[x][y] not empty or{             return;         }          set cellsMap[x][y] to count;         addTask(x,y);     }      function isInMapRange(x,y){         return x < cellsMap.length &&              x >= 0 &&             y < cellsMap[0].length &&              y >= 0;     }      function addTask(x, y)     {         initialize mapFilter;          set mapFilter.map = this.map         set mapFilter.cellsMap = this.cellsMap         set mapFilter.count = this.count + 1         set mapFilter.x = x         set mapFilter.y = y         add mapFilter to stack      } } 

Asked By : Ilya_Gazman

Answered By : D.W.

You have an unweighted, undirected graph with $N$ vertices, and where each vertex has degree $K$. Then the problem of computing shortest paths can be solved in $O(KN)$ time using simple breadth-first search.

Why is this faster than Floyd-Warshall etc.? Because Floyd-Warshall has to handle weighted graphs. In your case you have an unweighted graph: every edge has weight 1 (the length of a path is just the number of edges in it). There are faster algorithms for computing shortest paths in unweighted graphs than in weighted graphs; unsurprisingly, the problem is harder if you have a weighted graph. If you have an unweighted graph, you don't need the fancier algorithms, like Floyd-Warshall; breadth-first search is enough.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/27521