This is a program I just recently completed for a computer science course. Given a 2D grid, where every path between two gridpoints has a weight (path length) associated with it, this program computes the shortest path from (1,1) to (m,n). You are only allowed to move up and to the right (so no, it's not Dijstra.)

```
// 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

I'm a super-geeky programmer with a passion for Internet marketing. :)