trouvez le chemin le plus court dans un labyrinthe de nombres, Java

Après avoir cherché sur BFS, maintenant je connais la différence entre DFS et BFS. L'algorithme DFS parcourt un chemin de la source au dernier nœud, si l'objectif est trouvé stop, sinon essayez à nouveau un autre chemin de la source au dernier nœud, et ainsi de suite jusqu'à ce que l'objectif soit atteint. Alors que l'algorithme BFS se déplace de la source au niveau ci-dessous, si l'objectif est trouvé arrêter, sinon aller au niveau suivant et ainsi de suite.. Pour mon problème, BFS est un algorithme approprié pour trouver le chemin le plus court. Le code après certains modifications:

public class findShoretstPath
{
    private static class Node 
    {
        private int[] coordinate = new int[2];
        private int data;
        private Node Right, Left, Top, Bottom;
        public Node(){}
    }


public static boolean isLinked(Node s, Node d) //method to determine if the node d is linked to the node s
{
    if(d.Right == s) return true;
    if(d.Bottom == s) return true;
    if(d.Left == s) return true;
    if(d.Top == s) return true;
    return false;
}

public static boolean isValid(int[][] a, int x, int y)
{
   if(x >= 0 && x < a.length && y >= 0 && y < a.length) 
       return true;
   return false;
}

public static Node[][] nodeArray(int[][] a)
{
    Node[][] nodeA = new Node[a.length][a.length];
    for(int i = 0; i<nodeA.length; i++)
        for(int j = 0; j<nodeA[i].length; j++)
        {
            nodeA[i][j] = new Node();
            nodeA[i][j].coordinate[0] = i;
            nodeA[i][j].coordinate[1] = j;
            nodeA[i][j].data = a[i][j];
        }
    for(int i = 0; i<nodeA.length; i++)
        for(int j = 0; j<nodeA[i].length; j++)
        {
            if(isValid(a, i, j+nodeA[i][j].data))
                nodeA[i][j].Right = nodeA[i][j+nodeA[i][j].data];
            if(isValid(a, i, j-nodeA[i][j].data))
                nodeA[i][j].Left = nodeA[i][j-nodeA[i][j].data];
            if(isValid(a, i+nodeA[i][j].data, j))
                nodeA[i][j].Bottom = nodeA[i+nodeA[i][j].data][j];
            if(isValid(a, i-nodeA[i][j].data, j))
                nodeA[i][j].Top = nodeA[i-nodeA[i][j].data][j];
        }
    return nodeA;
}

public static void shortestPath(Node[][] nodes, int x, int y)
{
    Stack<Node> stack = new Stack<>();
    Queue<Node> queue = new LinkedList<>();
    int[][] path = new int[nodes.length][nodes[0].length];
    boolean b = false;
    int level = 1;//to keep tracking each level viseted
    queue.add(nodes[x][y]);
    path[x][y] = level;
    while(!queue.isEmpty())
    {
        Node temp;
        level++;
        int size = queue.size();
        for(int i = 0; i<size; i++)
        {
            temp = queue.remove();
            if(temp.data == -1) {b = true; break;}
            if(temp.Right != null && path[temp.Right.coordinate[0]][temp.Right.coordinate[1]] == 0)
            {
                queue.add(temp.Right);
                path[temp.Right.coordinate[0]][temp.Right.coordinate[1]] = level;
            }
            if(temp.Bottom != null && path[temp.Bottom.coordinate[0]][temp.Bottom.coordinate[1]] == 0)
            {
                queue.add(temp.Bottom);
                path[temp.Bottom.coordinate[0]][temp.Bottom.coordinate[1]] = level;
            }
            if(temp.Left != null && path[temp.Left.coordinate[0]][temp.Left.coordinate[1]] == 0)
            {
                queue.add(temp.Left);
                path[temp.Left.coordinate[0]][temp.Left.coordinate[1]] = level;
            }
            if(temp.Top != null && path[temp.Top.coordinate[0]][temp.Top.coordinate[1]] == 0)
            {
                queue.add(temp.Top);
                path[temp.Top.coordinate[0]][temp.Top.coordinate[1]] = level;
            }
        }
        if(b) break;
    }
    if(b)
    {
        int x1 = 0, y1 = 0;
        for(int i = 0; i<nodes.length; i++)// to locate the position of the goal
            for(int j = 0; j<nodes.length; j++)
                if(nodes[i][j].data == -1)
                {
                    x1 = i; y1 = j;
                }
        stack.add(nodes[x1][y1]);
        int d = path[x1][y1];
        while(d > 0)//go back from the goal to the source
        {
           for(int i = 0; i<path.length; i++)
           {
               if(path[x1][i] == d-1 && isLinked(nodes[x1][y1], nodes[x1][i]))
               {
                  stack.add(nodes[x1][i]);
                  y1 = i;
                  break;
               }
               else if(path[i][y1] == d-1 && isLinked(nodes[x1][y1], nodes[i][y1]))
               {
                  stack.add(nodes[i][y1]);
                  x1 = i;
                  break;
               }
           }
           d--;
        }
        Node temp;
        int stackSize = stack.size();
        for(int i = 0; i<stackSize; i++)// print the final result
        {
           temp = stack.pop();
           System.out.print("("+temp.coordinate[0]+" "+temp.coordinate[1]+") ");
        }
    }
    else System.out.print("No Solution Possible.");
}
public static void main(String[] args)
{
       int[][] maze = {{1,1,1,1,1},
                       {1,1,1,1,1},
                       {1,1,1,1,1},
                       {1,1,1,1,3},
                       {4,1,1,3,-1}};
        Node[][] net = nodeArray(maze);
        shortestPath(net, 0, 0));
        System.out.println("");
}
}

Et la sortie est maintenant:

(0 0) (1 0) (2 0) (3 0) (4 0) (4 4)