# Shortest path from starting cell to all cells in the grid

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;
}

function isInMapRange(x,y){
return x < cellsMap.length &&
x >= 0 &&
y < cellsMap.length &&
y >= 0;
}

{
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

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.