University of Central Florida Algorithms & Data Structures for Road Routes Project

I’m working on a algorithms & data structures project and need support to help me study.

I’m working on a algorithms & data structures project and need a reference to help me learn.

The language used for this project is C++

AlsoI thank anyone attempting this, this is the reality of inexperiencedprofessors that put us students through so much. Please help me if youcan. Thank you so much, very much appreciated.

youwill develop algorithms that find road routes through the bridges totravel between islands.The input is a text file containing data aboutthe given map. Each file begins with the number of rows and columns inthe map considered as maximum latitudes and maximum longitudesrespectively on the map. The character “X” in the file represents thewater that means if a cell contains “X” then the traveler is not allowedto occupy that cell as this car is not drivable on water. The character”0″ in the file represents the road connected island. That means if acell contains “0” then the traveler is allowed to occupy that cell asthis car can drive on roads.

The traveler starts at the islandlocated at latitude = 0 and longitude = 0 (i.e., (0,0)) in the upperleft corner, and the goal is to drive to the island located at(MaxLattitude-1, MaxLongitudes-1) in the lower right corner. A legalmove from an island is to move left, right, up, or down to animmediately adjacent cell that has road connectivity which means a cellthat contains “0”. Moving off any edge of the map is not allowed.

Print paths as explicitly specified for all the functions in Part A, Part B, and extra credit on the console.

Input: The map files

Output: Print paths as explicitly specified for all the functions in Part A, Part B, and extra credit on the console.

Part A

Consider the following class map,

class map

{

public:

map(ifstream &fin);

void print(int,int,int,int);

bool isLegal(int i, int j);

void setMap(int i, int j, int n);

int getMap(int i, int j) const;

int getReverseMapI(int n) const;

int getReverseMapJ(int n) const;

void mapToGraph(graph &g);

bool findPathRecursive(graph &g, stack<int> &moves);

bool findPathNonRecursive1(graph &g, stack<int> &moves);

bool findPathNonRecursive2(graph &g, queue<int> &moves);

bool findShortestPath1(graph &g, stack<int> &bestMoves);

bool findShortestPath2(graph &, vector<int> &bestMoves);

void map::printPath(stack<int> &s);

int numRows(){return rows;};

int numCols(){return cols;};

private:

int rows; // number of latitudes/rows in the map

int cols; // number of longitudes/columns in the map

matrix<bool> value;

matrix<int> mapping; // Mapping from latitude and longitude co-ordinates (i,j) values to node index values

vector<int> reverseMapI; // Mapping from node index values to map latitude i value

vector<int> reverseMapJ; // Mapping from node index values to map longitude j value

};

1.Using the above class map, write function void map::mapToGraph(graph&g){…} to createe a graph g that represents the legal moves in themap m. Each vertex should represent a cell, and each edge shouldrepresent a legal move between adjacent cells.

2. Writee arecursive function findPathRecursive(graph &g, stack<int>&moves) that looks for a path from the start island to thedestination island. If a path from the start to the destination exists,your function should call the map::printPath() function that shouldprint a sequence of correct moves (Go left, Go right, Go down, Go up,etc.). If no path from the start to the destination exists, the programshould print, “No path exists”. If a solution exists the solver shouldalso simulate the solution to each map by calling the map::print()function. Hint: consider recursive-DFS.

3. Writee a functionfindPathNonRecursive1(graph &g, stack<int> &moves) thatdoes the same thing as in 2, but by using stack and without usingrecursion. If a path from the start to the destination exists, yourfunction should call the map::printPath() function that should print asequence of correct moves (Go left, Go right, Go down, Go up, etc.). Ifno path from the start to the destination exists, the program shouldprint, “No path exists”. If a solution exists the solver should alsosimulate the solution to each map by calling the map::print() function.Hint: consider stack-based DFS.

4. Writee a functionfindPathNonRecursive2(graph &g, queue<int> &moves) thatdoes the same thing as in 2, but by using queue and without usingrecursion. If a path from the start to the destination exists, yourfunction should call the map::printPath() function that should print asequence of correct moves (Go left, Go right, Go down, Go up, etc.). Ifno path from the start to the destination exists, the program shouldprint, “No path exists”. If a solution exists the solver should alsosimulate the solution to each map by calling the map::print() function.Hint: consider queue-based BFS.

Part B

The shortest path on amap is a path from the start to the destination with the smallestnumber of intermediate islands, that is the path with the least numberof intermediate “0”.

1. Write two functionsfindShortestPath1(graph &g, stack<int> &bestMoves) andfindShortestPath2(graph &g, stack<int> &bestMoves) thateach finds the shortest path on a map if a path from the start to thedestination exists. The first algorithm should use Dijkstra algorithmand the second algorithm should use Bellman-Ford algorithm to find theshortest paths. In each case, if a solution exists the solver shouldcall the map::printPath() function that should print a sequence ofcorrect moves (Go left, Go right, Go down, Go up, etc.). If no path fromthe start to the destination exists, the program should print, “No pathexists”. If a solution exists the solver should also simulate thesolution to each map by calling the map::print() function. Each functionshould return true if any paths are found, and false otherwise.

.pdf file | C++-