1
$\begingroup$

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 
    }
}
$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.