Hi all,
i have written a very simple function to find a shortest path through a matrix, where each Node has a value, and the final return value is the minimal cost to cross from starting point to end point while adding all values on the way.
It works fine for matrices up to 6*6, but when I try bigger ones, it hangs.
I'm not very fluent with algorithms, can someone help me find a more efficient algorithm?
on the code side:
All .status are started with "=CLOSED".
"LARGE" is defined to be "MAX_LONG"

long int GetMin(Node** matrix,int currentR,int currentC,int endR,int endC,
				int rows,int columns)
{
	long int result;
	//if out of bounds return max of field
	if (currentR==rows || currentC==columns || currentR<0 || currentC<0)
		return LARGE;

	//if reached end
	if (currentC==endC && currentR==endR)
		return (matrix[currentR][currentC].value);

	//if already checked here
	if (matrix[currentR][currentC].status==OPEN)
		return LARGE;
	//if not reached end	
	matrix[currentR][currentC].status=OPEN;
	result=Smallest4(
		GetMin(matrix,currentR,currentC+1,endR,endC,rows,columns),
		GetMin(matrix,currentR,currentC-1,endR,endC,rows,columns),
		GetMin(matrix,currentR+1,currentC,endR,endC,rows,columns),
		GetMin(matrix,currentR-1,currentC,endR,endC,rows,columns));

	//set current status to closed- can try here again	
	matrix[currentR][currentC].status=CLOSED;
	
	//if was blocked all directions
	if (result==LARGE)
		return LARGE;

	return matrix[currentR][currentC].value+result;
}

 

I'll bet your problem is right here:

result=Smallest4(
		GetMin(matrix,currentR,currentC+1,endR,endC,rows,columns),
		GetMin(matrix,currentR,currentC-1,endR,endC,rows,columns),
		GetMin(matrix,currentR+1,currentC,endR,endC,rows,columns),
		GetMin(matrix,currentR-1,currentC,endR,endC,rows,columns));

I don't see a definition for Smallest4() -- I'm assuming it's another function-- but each time it is called, there are four recursive calls to GetMin(), one for each neighbor of the cell in the current row and current column. And each of those cells calls GetMin() four times, so you have exponential growth in the number of recursive function calls.

You're most likely running out of stack space due to all of those calls to GetMin. Each time a function is called, the parameters and the return address are pushed onto the stack. When the function returns to its caller, that space is reclaimed, but not before then. This is why recursive functions, such as to compute the factorial of a number, are easy to code, but not very practical for large values.

I don't know that there's an easy fix for this function. You'll probably have to rethink it completely so as not to use recursion. You know more about this problem than I do, but maybe an approach as follows this might work.

For an n x n matrix, you should be able to find a path through it with somewhere between n and n^2 cells. Starting at the 1,1 entry of your matrix, check the cells adjacent to it for the cell with the minimum value. Keep track of which cell this was in an auxiliary matrix of some kind. Move to the cell with minimum value. Check the cells adjacent to it. Note which cell it is, and move to that cell, and so on, until you are across the matrix or run off its boundary.

Again, you know this problem better than I do, so I might not have gotten exactly what you're trying to do, but maybe this will be of help.

Mark