Minimal and Maximal Reward Routes in a Directed Acyclic Graph

(for more details view the documnet. Deliverables are mentioned in the document). The problem of route selection in a graph: there are several algorithms to find any route from point ’A’ to point ’B’, and there are several algorithms to find an optimal route (whatever optima might mean: shortest hop-count; minimal cost; and-so-on). There is often no guidance in the difference between an optimal solution and a solution that might not be optimal. This is what we will explore in this project, where you will be asked to find both the minimally optimal, as well as the maximally optimal route between the end points in a grid. You will be given one or more grids: An m-by-n grid has m n grid-cells, G[i; j], and each grid-location [i; j] has an associated reward R[i; j]. You can assume that m and n are larger than 2 and that rewards are natural numbers. A valid path from G[1; 1] to G[m; n] for this project, is a sequence P of grid-locations from [1; 1] to [m; n] so that 1. The path starts with location G[1; 1] and either location G[1; 2] or G[2; 1] is on the path. 2. If location G[1; j] with j < n is on he path, then either location G[1; j + 1] or G[2; j] is on the path. 3. If location G[i; 1] with i < m is on the path, then either location G[i; 2] or G[i + 1; 2] is on the path. 4. If location G[i; j] with 1 < i < m and 1 < j < n is on the path. then either location G[i + 1; j] or G[i; j + 1] is on the path. 5. If location G[i; n] with i < m is on the path, then so is location G[i + 1; n]. 6. If location G[m; j] with j < n is on the path, then so is location G[m; j + 1]. 7. The path ends with location G[m; n].