0

```
// DANI HOROWITZ
// NOVEMBER 2004
/***************************************************************************/
/***************************************************************************/
// CSC 155 Project 2 Dynamic Programming
// Assigned 11/02/2004
// Due : 11/16/2004
//
//
#include <iostream.h>
int *Rectangular_Shortest_Path(int , int , int , int , int[][6], int[][6]);
int *Rectangular_Shortest_Path(int startx, int starty, int endx, int endy,
int r[][6], int a[][6])
{
// I could find no easy way to dynamically create a 2D array in C++
int distance[10][10]; // keep track of distances to get to each point
int path[10][10]; // keep track of the best paths
/***************************************************************************/
/***************************************************************************/
int size = (endx-startx)+(endy-starty); // size of our shortest path array
int* shortest_path = new int[size]; // it will take 8 steps to get from (0,0)->(5,5)
cout << "It will take " << size << " steps" << endl;
/***************************************************************************/
/***************************************************************************/
// populate our starting place
distance[startx][starty] = 0;
// populate bottom distance row
for (int x=startx+1; x<=endx; x++)
{
distance[x][starty] = distance[x-1][starty] + r[x-1][starty];
cout << "We went right to get to (" << x << "," << starty << ") in " << distance[x][starty] << " units" << endl;
}
// populate leftmost distance row
for (int y=starty+1; y<=endy; y++)
{
distance[startx][y] = distance[startx][y-1] + a[startx][y-1];
cout << "We went up to get to (" << startx << "," << y << ") in " << distance[startx][y] << " units" << endl;
}
/***************************************************************************/
/***************************************************************************/
cout << endl;
for (int y=starty+1; y<=endy; y++) // go down each column
{
for (int x=startx+1; x<=endx; x++) // go across each row
{
int distance_up = distance[x][y-1] + a[x][y-1]; // calculate weight to get to (x,y) from coordinate below it
int distance_right = distance[x-1][y] + r[x-1][y]; // calculate weight to get to (x,y) from coordinate to left of it
if (distance_up < distance_right) // it's better to move up
{
distance[x][y] = distance_up; // populate our distance array
path[x][y] = 1; // populate our path array
cout << "If we go up to get to (" << x << "," << y << ") we can do it in a weight of " << distance[x][y] << " units" << endl;
}
else // it's better to move right
{
distance[x][y] = distance_right; // populate our distance array
path[x][y] = 0; // populate our path array
cout << "If we go right to get to (" << x << "," << y << ") we can do it in a weight of " << distance[x][y] << " units" << endl;
}
}
}
/***************************************************************************/
/***************************************************************************/
x = endx;
y = endy;
int n=0;
cout << endl << "Working backwards ..." << endl;
// now that we have all of the smaller problems solved to calculate the optimal weight to get to every point on the grid,
// let's figure out how to get from (5,5)->(1,1)
while (x >= startx && y >= starty) // loop so long as both coordinates are >= 1
{
if (x > startx && y > starty)
{
// we are not working in the first row or first column,
// which means that we have an opportunity of going left or down, whichever is best
if ((distance[x-1][y]+r[x-1][y]) < (distance[x][y-1]+a[x][y-1]))
{
cout << "Go left from (" << x << "," << y << ") for " << distance[x][y] << " units left" << endl;
x--; // move one unit left
}
else
{
cout << "Go down from (" << x << "," << y << ") for " << distance[x][y] << " units left" << endl;
y--; // move one unit down
}
}
else
{
if (x == startx) // we are somewhere in the left column
{
// we don't have a choice, we can only move down
cout << "Go down from (" << x << "," << y << ") for " << distance[x][y] << " units left" << endl;
y--;
}
else // we are somewhere in the bottom row
{
// we don't have a choice, we can only move left
cout << "Go left from (" << x << "," << y << ") for " << distance[x][y] << " units left" << endl;
x--;
}
}
shortest_path[n] = path[x][y]; // populate our shortest path array - this line has an error ??
n++;
}
cout << endl;
/***************************************************************************/
/***************************************************************************/
return shortest_path; // return the shortest path BACKWARDS!
}
int main()
{
int Right[6][6]; // entry Right[i][j] contains the link distance
// between grid point (i,j) to (i+1, j);
int Above[6][6]; // entry Above[i][j] contains the link distance
// between grid point (i,j) to (i, j+1);
int *shortest_path; // the array for storing the shortest path
//
// read the inputs for the 2-dimensional arrays Right and Above
//
for (int i=1; i< 6; i++)
{
for (int j=1; j < 6; j++)
{
cout << "Please enter the link distance : Right[" << i << "," << j << "]\n";
cin >> Right[i][j];
cout << "Please enter the link distance : Above[" << i << "," << j << "]\n";
cin >> Above[i][j];
}
}
shortest_path = Rectangular_Shortest_Path(1,1,5,5, Right, Above);
return (0);
}
```

About the Author

The article starter has earned a lot of community kudos, and such articles offer a bounty for quality replies.