Your task is (1) to use a depth-first search to travel through the maze; and (2) to use Dijkstra’s shortest distance and shortest path algorithms as described amongst the websites below (Useful Websites include : http://www.cse.ust.hk/~dekai/271/notes/L10/L10.pdf, and https://www.cs.auckland.ac.nz/software/AlgAnim/dijkstra.html, and http://www.cse.ust.hk/faculty/golin/COMP271Sp03/Notes/MyL09.pdf ) by assuming weight to be 1 for each edge.
This could happen if there are more than 1 path connecting starting and ending maze cells. (Note: If other references need to be referenced for further explanations of the algorithms – this is also granted)
We assume a maze is read from a text file. A maze file starts with two integers representing the number of rows and the number of columns of the maze cell. A maze cell corner is represented by + and walls by “-“ (horizontal walls) and “|” (vertical walls). The below shows an example of maze files
4 5
+-+-+-+-+-+
| | |
+ +-+ +-+-+
| |
+-+ +-+-+ +
| | | | |
+-+-+ + + +
| | | | |
+-+-+-+-+-+
which represents a maze with cells in 4 rows and 5 columns. We already consider the left-top cell as the starting cell and the bottom-right cell as the ending cell. They are marked by “s” and “e” respectively in the above picture. However both markers are not in a maze file.
Please note in this representation, a cell with all four walls is written as
+-+
| |
+-+
If any of “-“ or “|” is missing, there is no wall on that side. The corner “+” is always there.
Your program must display a representation of the maze on screen as it is in a maze file. Since graphics is not a requirement for this subject, you can use the above text-based representation for this if you don't want to delve into Java's graphic facilities. After your algorithm has found out path from the start and the end, you program shall print the path by writing “v”, “^”, “<” and “>”. For the above maze, we know a path which can be printed as
+-+-+-+-+-+
V | | |
+ +-+ +-+-+
|> > > > >|
+-+ +-+-+ +
| | | |V|
+-+-+ + + +
| | | |V|
+-+-+-+-+ +
One of important steps in your program is to convert the text-based maze representation into a Graph object. Here is the way to represent a maze by a graph. Each cell becomes a graph vertex and there is no wall between two neighbouring cell, then there will be an edge in the graph representation. Please note that the corners “+” can be ignored. Actually corner marks are added for better visual effect. For the above maze, the graph looks like See image.
The ordinary Graph class is implemented by Michael Main which can be downloaded from his website or a copy of which can be obtained from the subject site on the Interact. In this class, the depth-first search algorithm has been implemented, including the facility to extract a path. However you may need to modify it to suit your case.
To use Dijkstra’s algorithm for the shorted path, please implement a new class for graphs with weighted edges. Either you use the ordinary Graph class as a superclass for your implementation, or you start it from scratch by following the pattern used in the ordinary Graph class.
Provide two extra methods to implement Dijkstra’s shortest distance and shortest path algorithms found in the website links below (Useful Websites include : http://www.cse.ust.hk/~dekai/271/notes/L10/L10.pdf, and https://www.cs.auckland.ac.nz/software/AlgAnim/dijkstra.html, and http://www.cse.ust.hk/faculty/golin/COMP271Sp03/Notes/MyL09.pdf ). Note: If other references need to be referenced for further explanations of the algorithms – this is also granted.
Please carefully read the algorithm explanation and examples included in the links so that you fully understand the whole algorithms.
The shortest path algorithms only differ from the base shortest distance algorithm in keeping a record of previous vertex for each vertex. It would be helpful to write a method for printing a path from the start vertex to a given vertex according to the required output.