Search code examples
javagraphshortest-pathmaze

Finding the shortest path in a maze graph using adjacency matrix

I have some troubles with solving of a particular problem that is to find the shortest path in the maze graph. Probably, I'm stucked because of the fact that the maze is initialized by a four dimensional array like adjacent = new boolean[height][width][height][width]; The first and second pair of indices specify a location in the graph in row/column formation. The graph looks like this:

XXXXXXXXXXXXX
..........X.X
X.XXX.XXX.X.X
X.X.X...X.X.X
X.X.XXX.XXX.X
X...X.....X..
XXXXXXXXXXXXX

The ArrayList must hold the locations of the vertices in the path, in order from start to end inclusive.

I've already written the constructor and connection method; however, I have trouble with the finding shortest path method. Here is the example of how I create the maze graph:

final int edges[][] = {{1, 0, 1, 1}, {1, 1, 1, 2}, {1, 1, 2, 1}, 
                {1, 2, 1, 3}, {1, 3, 1, 4}, {1, 4, 1, 5}, {1, 5, 1, 6}, 
                {1, 5, 2, 5}, {1, 6, 1, 7}, {1, 7, 1, 8}, {1, 8, 1, 9}, 
                {1, 9, 2, 9}, {1, 11, 2, 11}, {2, 1, 3, 1}, {2, 5, 3, 5}, 
                {2, 9, 3, 9}, {2, 11, 3, 11}, {3, 1, 4, 1}, {3, 3, 4, 3}, 
                {3, 5, 3, 6}, {3, 6, 3, 7}, {3, 7, 4, 7}, {3, 11, 4, 11}, 
                {4, 1, 5, 1}, {4, 3, 5, 3}, {4, 7, 5, 7}, {4, 11, 5, 11}, 
                {5, 1, 5, 2}, {5, 2, 5, 3}, {5, 5, 5, 6}, {5, 6, 5, 7}, 
                {5, 7, 5, 8}, {5, 8, 5, 9}, {5, 11, 5, 12}};

        MazeGraph maze = new MazeGraph(13, 7); 

        for (int[] edge : edges) 
            maze.connect(new Location(edge[0], edge[1]), new Location(edge[2], edge[3]));
Solution

  • First of all, this

    adjacent = new boolean[height][width][height][width];

    contradicts with this:

    The first and second pair of indices specify a location in the graph in row/column formation.

    It is column/row, not row/column.

    Dijkstra's algorithm should be implemented for your matrix. Quote:

    Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra's algorithm will assign some initial distance values and will try to improve them step by step.

    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. Set the initial node as current. Mark all other nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.

    3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. 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 B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value.

    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.

    5. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.

    6. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3.