Shortest path between two location in 2D matrix

Question

Here is a code that does path finder from index[0,0] looking for destination , example the value '9'. Should BFS or DFS do any better than the below algorithm? Any advice for better algorithms to accomplish the same?

using System;

public class Test
{
    public static int[,] matrix =
        {
            {1, 2, 8, 4},
            {3, 0, 3, 4},
            {4, 0, 2, 3},
            {5, 0, 32, 9}
        };

    public static   int[,] solution = new int[4,4];


    public static void Main()
    {
        int rows = matrix.GetLength(0);
        int cols = matrix.GetLength(1);

         FindPath( matrix, 9, rows, cols);
        // your code goes here
    }

    public static void FindPath(int[,] matrix, int destination, int rows, int cols)
    {
        bool[] visited = new bool[rows * cols];

        for(int i=0; i < rows; i++ )
        {
            for(int j =0; j < cols; j++)
            {
                solution[i,j] = 0;                  
            }
        }

        for(int i=0; i < rows*cols; i++ )
        {
            visited[i] = false; 
        }

        CountPath(0, 0, visited, rows, cols, 9);


        for(int i=0; i < rows; i++ )
        {
            for(int j =0; j < cols; j++)
            {
                Console.Write(" " + solution[i,j]);
            }

            Console.WriteLine("");
        }
    }

    public static bool CountPath(int row, int col, bool[] visited, int rows, int cols, int destination)
    {
        if(row < 0 || row >= rows || col < 0 || col >= cols || visited[row * cols + col] || matrix[row,col] == 0)
        {
            Console.WriteLine("False...");
            return false;   
        }
        Console.WriteLine(matrix[row,col]);
        Console.WriteLine(matrix[row,col]);


        if(matrix[row,col] == destination)
        {

            solution[row, col] = matrix[row,col];
            Console.Write("Found\n");
            return true;    
        }

        visited[row * cols + col] = true;
        solution[row, col] = matrix[row,col];

        Console.WriteLine(row);
        Console.Write(col);
        Console.WriteLine("-------------");

        bool hasdestination = CountPath(row + 1, col, visited, rows, cols, destination) ||
        CountPath(row , col + 1, visited, rows, cols, destination) ||
        CountPath(row - 1, col, visited, rows, cols, destination) ||
        CountPath(row , col - 1, visited, rows, cols, destination);

        if(!hasdestination)
        {
            Console.WriteLine("No luck go back...");
            solution[row, col] = 0;
            return false;           
        }

        return true;
    }
}

Answer 1

Your algorithm appears to be a simple recursive flood-fill search. It will search each location then check all of the surrounding locations. You have correctly implemented an "early out" for the grid edges, and for already searched locations, and it looks like you are treating matrix values of 0 as "walls" because they also trigger the "early out" exit.

The way you have stated this question is fairly unconventional. You mention searching for the value 9. Mostly search of this type is concerned with reaching a specific goal location (e.g. the value 9 is in location 4,4 of your matrix) and for that type of search either the A* algorithm or the Dijkstra modification will search fewer locations before finding the destination.

Principally, you need to specify what would be 'better' in this case? The usual judgement for the type of search I mentioned is that reducing the number of locations searched is 'better'. However there are cases where code simplicity may be more important, or where it is not necessary to know what the path is (as your example seems to imply), sometimes you need the guaranteed shortest path, and sometimes you just want a reasonably decent path. Every one of these cases and many more have been considered in some detail!

You may also want to rephrase your question as what you are doing is not strictly speaking path-finding. The algorithm you provided only indicates if a path exists, not what the steps of that path would be.

The expansion of your particular recursive function will cause it to search vertically down until it hits a wall or the grid edge. Then it will search one square to the right then again attempt to go downwards. If you print out the searched locations you'll quickly see what I mean when I say that this particular algorithm will search in a very eccentric fashion, and will only be efficient for search destinations which 'happen' to come early in the expansion pattern.