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);
}``````

While pursuing a Computer Science degree, I founded DaniWeb.com, an online community for developers and IT professionals. I coded the backend platform from the ground up and I also do all of the advertising sales and SEO. I'm a super-geeky programmer with a passion for Internet marketing.

3
Contributors
3
Replies
28
Views
13 Years
Discussion Span
Last Post by mohmedd

Sorry to be picky Dijstra isnt the matrix algorithm with weights - it is primm's matrix algorithm :p

I just looked it up to double check ... Dijstra is undirected and weighted. This algorithm provided is directed and weighted.

I want to distribute 200 sensors and 30 location in (10*10)m with sensing rang (1m),communication rang (2m),life time 1o hours . battery life(sensor) 6 hours and weight:1-10(random uniform disribute :
calculate total effective coverge time.
in c++

Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.