For this assignment, you will use Floyd's algorithm for determining the shortest path from one position in a map to another position in the map. The map consists of a matrix of characters, where each character symbolizes an obstacle with a specified cost to move into it:
Below is an example map, stored as a file:
15 15
...............
==..==.==.==^^^
..+++..=..^^^^^
.++++.==..^^^.^
..++..=........
..+...===....++
...............
..++++.........
...++..........
...............
^^^^=====......
^^^^=..........
.^^^=..========
..++.....=.....
....==.........
Your program should be able to read in such map, construct a matrix of shortest paths and lengths, and then respond to user requests for showing the shortest path from one specified position to another specified position. The following is an example run:
whoville% map
Which file?
map2.dat
Please wait while computer searches for good paths
***************
Start position (row and col)?
Type -1 -1 to exit program
1 15
End position (row and col)?
15 1
..........*****
==..==.==*==^^^
..+++..=*.^^^^^
.++++.==*.^^^.^
..++..=.*......
..+...===*...++
........*......
..++++.*.......
...++..*.......
........*......
^^^^=====*.....
^^^^=.***......
.^^^=*.========
.*++*....=.....
*.**==.........
Start position (row and col)?
To exit program, type -1 -1
1 1
End position (row and col)?
15 15
**.............
==*.==.==.==^^^
.*+++..=..^^^^^
.+*++.==..^^^.^
..+*..=........
..+.*.===....++
.....*.........
..++++*........
...++..*.......
........*......
^^^^=====*.....
^^^^=..**......
.^^^=.*========
..++...**=****.
....==...*....*
Start position (row and col)?
To exit program, type -1 -1
1 1
End position (row and col)?
2 2
A legal path does not exist!
Start position (row and col)?
To exit program, type -1 -1
-1 -1
whoville%
Some of the work has already been started for you. The Map class is defined and has a function for reading in the map file. Also, a private function has been written that initializes the contents of the matrices that will eventually store the shortest paths and lengths. You will still need to implement the functions for building the paths and for displaying the path whose endpoints are specified by the user. Also supplied is a simple driver program for initially testing your class. Of course, you will need to further develop this code so that it runs as above. Finally, a makefile is provided that compiles the entire project.
The arrays for building and maintaining the shortest paths and lengths are
slightly more complicated than what is presented in the text and in class.
Rather than labeling a position (i.e. vertex) with a scalar value, a
position for the map domain is labeled with two integer values, namely the
row and the column. For example, the pathLengths matrix (really a matrix
of a matrix) builds and maintains the shortest paths where
pathLengths[iRow][iCol][jRow][jCol] is the length of the shortest
path starting from position iRow, iCol and going to position
jRow, iCol. Whereas a simple for loop would systematically
run through the list of vertices in the algorithm presented in class, a
nested pair of for loops is required to run through the entire set of map
positions.
The matrix paths[iRow][iCol][jRow][jCol] stores an
intermediate position on the shortest path from position iRow,
iCol and going to position jRow, iCol. Because the
intermediate position is specified by two integers (as do all map
positions), the Position struct, which contains two integers, is declared
and used for the values of this matrix. Position values of -1 indicate
that the path has no intermediate positions.
For this assignment, infinity is represented as the largest integer value (defined by the const declaration LARGE_INT). Care must be taken, however, not to add LARGE_INT to any value since the resulting sum will not be LARGE_INT (unlike true infinity).