Java Maze shortest path 2d int array

Question

I'm currently stuck on a project. My goal is to use Dijkstra's algorithm.

I understand that I start from the point (0,0). I look at two nodes near the starting point, and then first go to a minimum and look at the surrounding nodes. My labyrinth is random, but to make it easy to start, let's say that this is my labyrinth.

I will start with (0,0) and want to end with (9,9), the numbers are the DANGER level, and we strive to ensure that the safest way is not the shortest.

I need a push to figure out how to set this up. I know I need a list or path to save where I am and where I want to look. but i don't know how to do this in java.

import java.awt.Point;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;


public class solver {

    /**
     * @param args
     */
    public static int[][]maze;
    public static int[][]openlist;
    public static int[][]closed;
    public static int[][]copy;
    public static int danger;
    public static int size=100;
    static int Max=9;
    static int Min=0;
    public static List path = new ArrayList();
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        maze = new int[size][size];
        openlist = new int[size][size];
        closed = new int[size][size];
        copy = new int[size][size];
        filler(maze);
        copy=dijstkra();
        printer(maze);
        //printer(copy);
        EDSfAO(maze,0,0);
        printer(openlist);
        printer(copy);
    }
    private static Boolean notwall(int i, int j){

        if((i>maze.length-1)||(j>maze.length-1)||(i<0)||(j<0))
        {return false;}

        return true;}
    private static int[][] dijstkra(){


        for(int i=0;i<maze.length;i++){
            for(int j=0;j<maze.length;j++){
                copy[i][j]=100000000;
            }}
        copy[0][0]=0;
        return copy;
        }

    private static void EDSfAO(int[][] maze,int i,int j){
        int min=100000000;
        int holdx = 0;  
        int holdy = 0;
        openlist[i][j]=1;
        danger=copy[i][j];
        if(i==maze.length-1&&j==maze.length-1){

            printer(copy);
            for(holdx=0;holdx<path.size();holdx++){

                System.out.print(path.get(holdx));

            }


        }
        else{
        if(notwall(i+1,j)&&openlist[i+1][j]!=1){
            copy[i+1][j]=danger+maze[i+1][j];
        } if(notwall(i,j+1)&&openlist[i][j+1]!=1){
            copy[i][j+1]=danger+maze[i][j+1];
        } if(notwall(i,j-1)&&openlist[i][j-1]!=1){
            copy[i][j-1]=danger+maze[i][j-1];
        } if(notwall(i-1,j)&&openlist[i-1][j]!=1){
            copy[i-1][j]=danger+maze[i-1][j];
        }
        for(int x=0;x<maze.length;x++){
            for(int y=0;y<maze.length;y++){

            if(openlist[x][y]!=1){

                if(min>copy[x][y]){
                min=copy[x][y];
                holdx=x;    
                holdy=y;
                }

            }


        }}
        moveToPosition(holdx,holdy);
        }
    }


    private static void moveToPosition(int x, int y) {

            openlist[x][y]=1;
            path.add("("+x+","+y+")");
            openlist[x][y]=1;
            EDSfAO(maze,x,y);
    }

private static void printer(int[][] maze) {
        // TODO Auto-generated method stub
    for(int i=0;i<maze.length;i++){
        for(int j=0;j<maze.length;j++){
        System.out.print("["+maze[i][j]+"]");                       
        }
        System.out.println();
        }

    }

public static void filler(int[][] maze){

        for(int i=0;i<maze.length;i++){

            for(int j=0;j<maze.length;j++){
            //If i=0 AND j=0 then maze[0][0]= 0(start) OR i= maze.length-1 AND j= maze.length-1 then maze[maze.length][maze.length]=0
            if((i==0 && j==0) || (i==maze.length-1 && j==maze.length-1)){

                maze[i][j]=0;   

            }else{
                maze[i][j]=Min + (int)(Math.random() * ((Max - Min) + 1));
            }
            }
            }
    }
}

, - .   , . dijstkra, .

, , node 100000000, node (0,0) 0.

- , , .

UPDATE:

, . , , , , - .

, 100X100, - , ? " ". , ( ); , , .

---

" ", . , 0 () 9 ( ). , , .

, , , , , ( ). (0,0), (n-1, n-1).

"", , , .

:

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

= 11

100 100 , 0-9. (, 10 000 - , , , , , , . ) *

* . ...

( , , " " ). .

UPDATE2: .

if(min>copy[x][y]){
                min=copy[x][y];
                holdx=x;    
                holdy=y;
                }

, , , , ?

? .

Answer 1

Dijkstra Algorithm.

• node : node .
• . node . , , node.
• node, . , node A 6, , B 2, B ( A) 6 + 2 = 8. , , . , , .
• node, node . node ; .
• , . .
• node " node" 3.

. , " ". 2- . node " ". , i, j. -, / tentative_distance_value j.

, node. .

" node". , .

, . , . , java.

, . , , , , , .

Answer 2

, , ArrayList , :

List<Point> path = new ArrayList<Point>();

Point, int, x y.

, , :

private void moveToPosition(int x, int y) {
    path.add(new Point(x, y));

    // Move yourself to this point
    ...
}

, , , , !

, , .

Answer 3

, " " Cormen, Leiserson, Rivest Stein, 2nd Edition. 24 " ", 24.3 .

. , ​​ Java. , , . Java , .

, , 2D-, : int [M] [N] . - , - , . , 0 M-1 0 N-1 . [] [] , (, ). , , .

, : row1, row2,..., rowM. . , : (, ) → → (, ).

convert_to_index(row, column) ::= row * N + column
convert_to_pair(i) ::= (i div N, i modulo N)

, SIZE - M * N, .

, : int [SIZE] [SIZE] adjacency_matrix, - FROM, - TO. , . , , . . , INFINITY. 0 9. , .

, (r, c), ? , . , : (r-1, c-1), (r-1, c), (r-1, c + 1), (r, c-1), (r, c + 1), (r + 1, c-1), (r + 1, c) (r + 1, c + 1). convert_to_index , , 0..SIZE-1 . , , (r, c) (r-1, c-1) [r-1, c-1] (r-1, c-1) (r, c) [r, c]. (r, c) 10, , .

adjacent_rooms(r, c) ::=
    Given the vector [(r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1,c+1)]
    Filter it by deleting pairs whose row is not in 0..M-1 or whose column is not in 0..N-1
    Then apply the function convert_to_index to each resulting pair (map operation)
    Return the result

for i in 0..SIZE-1 loop
    for j in 0..SIZE-1 loop
        adjacency_matrix[i, j] := -1
    end loop
end loop

for i in 0..SIZE-1 loop
    (current_r, current_c) := convert_to_pair(i)
    adjacent_room_indexes := adjacent_rooms(current_r, current_c)
    for j in 0..SIZE-1 loop
        if adjacency_matrix[i, j] == -1 then
            (r, c) := convert_to_pair(j)
            if i == j then adjacency_matrix[i, j] := 0
            elsif j in adjacent_room_indexes then adjacency_matrix[i, j] := maze[r, c]; adjacency_matrix[j, i] := maze[current_r, current_c]
            else adjacency_matrix[i, j] := INFINITY
        end if
    end loop
end loop

(. 585) (. 584).

for i in 0..SIZE-1 loop
    predecessors[i] := NONE
    estimates[i] := INFINITY
end loop

0.

estimates[0] := 0

, MST ( )

mst := empty set

- q

for i in 0..SIZE-1 loop
    q.add(i, estimates[i])
end loop

until q.empty? loop
    u, u_d = q.delete_min
    mst.add(u)
    (current_r, current_c) := convert_to_pair(i)
    adjacent_room_indexes := adjacent_rooms(current_r, current_c)
    for i in 0..adjacent_room_indexes.length-1 loop
        v := adjacent_room_indexes[i]
        cost = adjacency_matrix[u, v]
        if cost < q[v]
          predecessors[v] = u
          estimates[v] = c
          q[v] = c
        end
    end loop
end loop

. predecessors estimates.

, A * . , Dijkstra . A *, A * Pathfinding Amits A * Pages.

Answer 4

, ccoakley. , :

import java.util.HashSet;
import java.util.Set;

// 1. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
// 2. Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node.
// 3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded distance, then overwrite that distance. Even though a neighbor has been examined, it is not marked as visited at this time, and it remains in the unvisited set.
// 4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again; its distance recorded now is final and minimal.
// 5. If the unvisited set is empty, then stop. The algorithm has finished.
// 6. Set the unvisited node marked with the smallest tentative distance as the next "current node" and go back to step 3.
public class Dijkstra {

    class Node {
        String name;
        Integer distance = Integer.MAX_VALUE;
        boolean visited;
        Set<Edge> edges = new HashSet<Edge>();

        Node(String name) {
            this.name = name;
        }

        Edge connect(Node destination, int length) {
            Edge edge = new Edge();
            edge.length = length;
            edge.from = this;
            edge.to = destination;
            edges.add(edge);
            destination.edges.add(edge);
            return edge;
        }

        @Override
        public String toString() {
            return name;
        }
    }

    class Edge {
        int length;
        Node from;
        Node to;

        Node getNeighbor(Node origin) {
            if (from == origin) {
                return to;
            }
            else if (to == origin) {
                return from;
            }
            else {
                throw new IllegalArgumentException("This edge is not connected to node " + origin);
            }

        }

        @Override
        public String toString() {
            return String.format("%s-%s", from, to);
        }
    }

    /**
     * <pre>
     * a - b - c
     * |   |   
     * d - e   |
     * |
     * f - g - h
     * </pre>
     * 
     * @return
     */
    private Set<Node> initialize() {
        Node a = new Node("a");
        Node b = new Node("b");
        Node c = new Node("c");
        Node d = new Node("d");
        Node e = new Node("e");
        Node f = new Node("f");
        Node g = new Node("g");
        Node h = new Node("h");

        a.connect(b, 4);
        a.connect(d, 8);
        b.connect(c, 6);
        b.connect(e, 1);
        c.connect(h, 7);
        d.connect(e, 2);
        d.connect(f, 5);
        f.connect(g, 3);
        g.connect(h, 1);

        a.distance = 0;

        Set<Node> unvisited = new HashSet<Dijkstra.Node>();
        unvisited.add(a);
        unvisited.add(b);
        unvisited.add(c);
        unvisited.add(d);
        unvisited.add(e);
        unvisited.add(f);
        unvisited.add(g);
        unvisited.add(h);

        return unvisited;
    }

    private Set<Node> solve(Set<Node> unvisited) {

        Set<Node> visited = new HashSet<Node>();

        while (!unvisited.isEmpty()) {

            System.out.println(String.format("Unvisited nodes:%s", unvisited.size()));
            print(unvisited);
            Node current = findNodeWithSmallestDistance(unvisited);
            System.out.println(String.format("Current node:%s", current));
            updateNeighbors(current);
            current.visited = true;
            unvisited.remove(current);
            visited.add(current);
        }

        return visited;
    }   

    private void updateNeighbors(Node current) {

        for (Edge edge : current.edges) {    
            Node neighbor = edge.getNeighbor(current);
            if (!neighbor.visited) {
                int tentativeNeighborDistance = current.distance + edge.length;
                if (tentativeNeighborDistance < neighbor.distance) {
                    neighbor.distance = tentativeNeighborDistance;
                    System.out.println(String.format("Neighbor:%s distance:%s", neighbor, neighbor.distance));
                }
                else {
                    System.out.println(String.format("Neighbor:%s no shorter path     found", neighbor));
                }
            }
            else {
                System.out.println(String.format("Neighbor:%s already visited",     neighbor));
            }
        }
    }

    private Node findNodeWithSmallestDistance(Set<Node> nodes) {
        Node smallest = null;
        for (Node node : nodes) {
            if (smallest == null || node.distance < smallest.distance) {
                smallest = node;
            }
        }
        return smallest;
    }

    private void print(Set<Node> visited) {
        for (Node node : visited) {
            System.out.println(String.format("Node:%s has distance:%s", node, node.distance));
        }
    }

    public static void main(String[] args) {
        Dijkstra edsger = new Dijkstra();
        Set<Node> unvisited = edsger.initialize();
        Set<Node> visited = edsger.solve(unvisited);
        edsger.print(visited);
    }
}

EDIT: