GRAPH: find an algorithm for determining the shortest path from one point to another in a rectangular maze?

Question

GRAPH: find an algorithm for determining the shortest path from one point to another in a rectangular maze?

I get such a headache when trying to develop an appropriate algorithm to move from the START position to the EXIT position in the maze. For what it's worth, the maze is rectangular , maxsize 500x500 and, theoretically, can be resolved by DFS using some branching and binding methods ...

10 3 4  
7 6  
3  3  1  2  2  1  0  
2  2  2  4  2  2  5  
2  2  1  3  0  2  2  
2  2  1  3  3  4  2  
3  4  4  3  1  1  3  
1  2  2  4  2  2  1 

Output:
5 1 4 2

Explanation:
Our agent loses energy every time he takes a step, and he can only move up, down, left and right. In addition, if an agent arrives with a remaining energy of zero or less, he dies, so we print something like "Impossible."

, 10 , 3 4 - START (.. 3, 4) 7x6. , , ( ).

, , , , .

, DFS 500x500 , , .

The output means that the agent came with the remaining energy = 5 to the output pos 1 4 in 2 steps. If we look carefully, in this maze you can also go to pos 3 1 (column 3, line 1) with the same energy, but with 3 steps, so we choose the best.

With these considerations, can someone help me with some kind of code or pseudocode? I am having problems with a 2D array and how to save the remaining energy, path (or number of steps) ....

EDIT:

Larry, as I said, is a bit puzzled by the code. Here is what I have tried so far, only to determine the shortest path with smaller steps from START to EXIT, fixing EXIT in the meantime ...

public class exitFromMaze {

    int energy, startY, startX, xMax, yMax;
    int adjMatrix[][];
    boolean visited[][];
    ArrayList<Cell> neighbours;

    //ArrayList<Cell> visited;
    Cell start;
    Stack<Cell> stack;

    public exM() {
        Scanner cin = new Scanner(System.in);
        int nrTests = cin.nextInt();
        for (int i = 0; i < nrTests; i++) {
            energy = cin.nextInt();
            startY = cin.nextInt()-1; //start at columnstartY
            startX = cin.nextInt()-1; //start at line startX
            xMax = cin.nextInt();//7 cols
            yMax = cin.nextInt(); //8 rows

            adjMatrix = new int[yMax][xMax];
            visited = new boolean[yMax][xMax];
            //visited = new ArrayList<Cell>();
            this.stack = new Stack<Cell>();
            for (int r = 0; r < yMax; r++) { // yMax linhas
                for (int c = 0; c < xMax; c++) { // xMax colunas
                    adjMatrix[r][c] = cin.nextInt();
                    visited[r][c] = false;
                    //System.out.println("matrix["+r+"]["+c+"] = "+adjMatrix[r][c]);
                }
            }
            start= new Cell(startX, startY, 0);
            //adiciona a pos actual à pilha de celulas/nos
            stack.push(start);
            //printArray(yMax, xMax);
            findBestExit();
        }//end_of_test_Cases
    }

    private void findBestExit() {
        // BEGINNING OF DEPTH-FIRST SEARCH
        Cell curCell;

        while (!(stack.empty())) {
            curCell = (Cell) (stack.pop());
            //just fix an exit point ...for now (if it works for one, it has to work for all the other possible exits)
            if (curCell.row==0 && curCell.col== 4) {
                System.out.println("Arrived at pos: "+curCell.row+","+curCell.col+" with E= "+(energy-curCell.getEnergy())+" with "+curCell.getSteps()+" steps");
                //finish = curCell;
                break;
            } else {
                visited[curCell.row][curCell.col] = true;
            }
            this.neighbours = (ArrayList<Cell>) curCell.getNeighbours(this.xMax, this.yMax);
            for (Cell neighbourCell: neighbours) {
                //1- I think something missing here and it would be here the point to cut some cases...isn't it?
              if ( curCell.getEnergy() + neighbourCell.getEnergy() < this.energy && !visited[neighbourCell.row][neighbourCell.col]){
                  neighbourCell.energy+= curCell.energy;
                  neighbourCell.setSteps(curCell.getSteps()+1);
                  neighbourCell.setPrevious(curCell);
                  stack.push(neighbourCell);
              }
              // ...
            }
        }
        // END OF DEPTH-FIRST SEARCH and DIJKSTRA?
    }

    class Cell {

        int row;
        int col;
        int energy;
        int steps;
        Cell previous;
        //Node next;

        public Cell(int x, int y, int steps) {
            this.row = x;
            this.col = y;
            this.energy = adjMatrix[x][y];
            this.steps = steps;
            //this.next = null;
            this.previous = null;
        }

        public Cell(int x, int y, Cell prev) {
            this.row = x;
            this.col = y;
            this.steps = 0;
            this.energy = adjMatrix[x][y];
            this.previous = prev;
        }

        @Override
        public String toString() {
            return "(,"+this.getRow()+","+this.getCol()+")";
        }



        public int getEnergy() {
            return energy;
        }

        public void setEnergy(int energy) {
            this.energy = energy;
        }

        public Cell getPrevious() {
            return previous;
        }

        public void setPrevious(Cell previous) {
            this.previous = previous;
        }

        public int getRow() {
            return row;
        }

        public void setRow(int x) {
            this.row = x;
        }

        public int getCol() {
            return col;
        }

        public void setCol(int y) {
            this.col = y;
        }

        public int getSteps() {
            return steps;
        }

        public void setSteps(int steps) {
            this.steps = steps;
        }

        public Cell south(int verticalLimit) {
            Cell ret = null;
            if (row < (verticalLimit - 1)) {
                ret = new Cell(row+1, col, this);
                //ret.previous = this;
            }
            return ret;
        }

        /**
         * Gives the north to our current Cell
         * @return the Cell in that direction, null if it impossible
         * to go in that direction
         */
        public Cell north() {
            Cell ret = null;
            if (row > 0) {
                ret = new Cell(row-1, col ,this);
                //ret.previous = this;
            }
            return ret;
        }

        /**
         * Gives the west (left) to our current Cell
         * @return the Cell in that direction, null if it's
         * impossible to go in that direction
         */
        public Cell west() {
            Cell ret = null;
            if (col > 0) {
                ret = new Cell(row, col-1,this);
                //ret.previous = this;
            }
            return ret;
        }

        /**
         * Gives the east direction(right) to our current Cell
         * @return the Cell in that direction, null if it's
         * impossible to go in that direction
         */
        public Cell east(int horizontalLimit) {
            Cell ret = null;
            //if it inside the number max of collumns
            if (col < (horizontalLimit - 1)) {
                ret = new Cell(row , col+1, this);
            }
            return ret;
        }

        public List getNeighbours(int xlimit, int ylimit) {
            ArrayList<Cell> res = new ArrayList<Cell>(4);
            Cell n;
            n = south(ylimit);
            if (n != null) {
                res.add(n);
            }
            n = north();
            if (n != null) {
                res.add(n);
            }
            n = east(xlimit);
            if (n != null) {
                res.add(n);
            }
            n = west();
            if (n != null) {
                res.add(n);
            }
            return res;
        }
    }

    private void printArray(int h, int w) {
        int i, j;
        // print array in rectangular form
        System.out.print("   ");
        for (i = 0; i < w; i++) {
            System.out.print("\t" + i);
        }
        System.out.println();
        for (int r = 0; r < h; r++) {
            System.out.print("  " + r);
            for (int c = 0; c < w; c++) {
                System.out.print("\t" + adjMatrix[r][c]);
            }
            System.out.println("");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        new exM();
    }
}

To enter:

1  
40 3 3  
7 8  
12 11 12 11  3 12 12  
12 11 11 12  2  1 13  
11 11 12  2 13  2 14  
10 11 13  3  2  1 12  
10 11 13 13 11 12 13 
12 12 11 13 11 13 12  
13 12 12 11 11 11 11  
13 13 10 10 13 11 12

It should print:

12 5 1 8

those. agent output in the best yield (0.4), with remaining energy = 12 and in just 8 steps.

, , , ? ... - ...

/ ( ( > 0), ).

3 
40 3 3 
7 8  
12 11 12 11  3 12 12 
12 11 11 12  2  1 13  
11 11 12  2 13  2 14 
10 11 13  3  2  1 12 
10 11 13 13 11 12 13  
12 12 11 13 11 13 12  
13 12 12 11 11 11 11 
13 13 10 10 13 11 12 
8 3 4 
7 6 
4  3  3  2  2  3  2  
2  5  2  2  2  3  3  
2  1  2  2  3  2  2  
4  3  3  2  2  4  1  
3  1  4  3  2  3  1  
2  2  3  3  0  3  4  
10 3 4  
7 6  
3  3  1  2  2  1  0  
2  2  2  4  2  2  5  
2  2  1  3  0  2  2 
2  2  1  3  3  4  2  
3  4  4  3  1  1  3  
1  2  2  4  2  2  1  

Output 
12 5 1 8  
Goodbye cruel world!
5 1 4 2

+3

java algorithm graph

neverMind 14 . '10 3:14

3

Larry · Answer 1 · 2010-04-14T03:18:24+0000

Dijkstra algorithm, . O(V log V), 500x500. , node, , . node .

: :

function Dijkstra( graph, source ):
     // distance is infinity to everywhere initially
     dist = initialize list of size V to infinity 
     // no vertices pointed to anything
     previous = initialize list of size V to undefined

     // distance from source to source is 0
     dist[source] = 0

     Q = priority queue

     insert all vertices into Q

     while Q is not empty:
         // get the vertex closest to the source
         current_vertex = Q.pop

         if dist[current_vertex] == infinity
             break

         // these are the adjacent vertices in the four cardinal direction
         for each vertex next to current_vertex:
              // if it costs less energy to go to vertex
              //   from current_vertex
              if ( dist[current_vertex] + energy[vertex] < dist[vertex] )
                  dist[vertex] = dist[current_vertex] + energy[vertex]
                  previous[vertex] = current_vertex

              // Another if statement here to 
              //   minimize steps if energy is the same

     // Now after this is done, you should have the cheapest cost to 
     //   each vertex in "dist".  Take the cheapest one on the edge.

     // You can walk backwards on the "previous" to reconstruct the path taken.

, , -, .

DFS, , . , int, 2D- 3D- x-y-e, e - - , , .

: DFS O(H*W*E), E <= 30000, H, W <= 500 , , .

Jack · Answer 2 · 2010-04-14T03:20:22+0000

A * - , : . , , D * .. ( ) !

BFS, , , ..

Constantin · Answer 3 · 2015-07-05T14:12:41+0000

, , , . :

import java.util.ArrayList;
import java.util.List;

public class Maze {

  private static final char E = 'E';   // Ending position
  private static final char X = 'X';   // Wall
  private static final char O = ' ';   // Space
  private static final char L = 'L';   // Left
  private static final char R = 'R';   // Right
  private static final char U = 'U';   // Up
  private static final char D = 'D';   // Down

  private static final char FALSE = '0';   // Not accessible
  private static final char TRUE = '1';    // Is accessible
  private static final Node END_NODE = new Node(4, 4);

  public static void main(String[] args) {

    char[][] maze = new char[][] { 
      {X, X, X, X, X, X},
      {X, O, O, X, O, X},
      {X, O, X, X, O, X},
      {X, O, O, O, X, X},
      {X, X, O, X, O, X},
      {X, O, O, O, O, X},
      {X, O, X, X, O, X},
      {X, X, X, X, X, X}};

    // PLOT THE DESTINATION CELL AND ADD IT TO LIST
    List<Node> nodes = new ArrayList<Node>();
    nodes.add(END_NODE);
    maze[END_NODE.row][END_NODE.col] = E;

    // PRINT THE MAZE BEFORE ANY CALCULATIONS
    printMaze(maze);

    // SOLVE THE MAZE
    fillMaze(maze, nodes);
    printMaze(maze);

    // CONVERT MAZE TO AN ADJACENCY MATRIX
    compileMaze(maze);
    printMaze(maze);
  }

  /**
   * The parallel arrays define all four directions radiating from
   * the dequeued node location. 
   * 
   * Each node will have up to four neighboring cells; some of these
   * cells are accessible, some are not. 
   * 
   * If a neighboring cell is accessible, we encode it with a directional
   * code that calculates the direction we must take should we want to 
   * navigate to the dequeued node location from this neighboring cell.
   * 
   * Once encoded into our maze, this neighboring cell is itself queued 
   * up as a node so that recursively, we can encode the entire maze.
   */
  public static final void fillMaze(char[][] maze, List<Node> nodes) {
    int[] rowDirections = {-1, 1,  0, 0};  
    int[] colDirections = { 0, 0, -1, 1};

    // dequeue our first node
    Node destination = nodes.get(0);
    nodes.remove(destination);

    // examine all four neighboring cells for this dequeued node
    for(int index = 0; index < rowDirections.length; index++) {
      int rowIndex = destination.row + rowDirections[index];
      int colIndex = destination.col + colDirections[index];

      // if this neighboring cell is accessible, encode it and add it
      // to the queue
      if(maze[rowIndex][colIndex] == O) {
        maze[rowIndex][colIndex] = getOppositeDirection(rowDirections[index], colDirections[index]);
        nodes.add(new Node(rowIndex, colIndex));
      }
    }
    // if our queue is not empty, call this method again recursively 
    // so we can fill entire maze with directional codes
    if(nodes.size() > 0) {
      fillMaze(maze, nodes);
    }
  }

  /**
   * Converts the maze to an adjacency matrix. 
   */
  private static void compileMaze(char[][] maze) {
    for(int r = 0; r < maze.length; r++) {
      for(int c = 0; c < maze[0].length; c++) {
        if(maze[r][c] == X || maze[r][c] == O) {
          maze[r][c] = FALSE;
        }
        else {
          maze[r][c] = TRUE;
        }
      }
    }
  }

  /**
   * prints the specified two dimensional array 
   */
  private static final void printMaze(char[][] maze) {
    System.out.println("====================================");
    for(int r = 0; r < maze.length; r++) {
      for(int c = 0; c < maze[0].length; c++) {
        System.out.print(maze[r][c] + "  ");
      }
      System.out.print("\n");
    }
    System.out.println("====================================");
  }

  /**
   * Simply returns the opposite direction from those specified 
   * by our parallel direction arrays in method fillMaze. 
   * 
   * coordinate 1, 1 is the center of the char[][] array and 
   * applying the specified row and col offsets, we return the
   * correct code (opposite direction)
   */
  private static char getOppositeDirection(int row, int col) {
    char[][] opposites = new char[][] {{O, D, O},{R, O, L},{O, U, O}};
     return opposites[1 + row][1 + col];
  }
}

class Node {
  int row;
  int col;

  public Node(int rowIndex, int colIndex) {
    row = rowIndex;
    col = colIndex;
  }
}

====================================
X  X  X  X  X  X  
X        X     X  
X     X  X     X  
X           X  X  
X  X     X  E  X  
X              X  
X     X  X     X  
X  X  X  X  X  X  
====================================
====================================
X  X  X  X  X  X  
X  D  L  X     X  
X  D  X  X     X  
X  R  D  L  X  X  
X  X  D  X  E  X  
X  R  R  R  U  X  
X  U  X  X  U  X  
X  X  X  X  X  X  
====================================
====================================
0  0  0  0  0  0  
0  1  1  0  0  0  
0  1  0  0  0  0  
0  1  1  1  0  0  
0  0  1  0  1  0  
0  1  1  1  1  0  
0  1  0  0  1  0  
0  0  0  0  0  0  
====================================

GRAPH: find an algorithm for determining the shortest path from one point to another in a rectangular maze?

More articles: