The only way to prevent overflow in all circumstances is to use BigInteger

Solved

Posted on 2004-11-29

I have a formula below which gives me weights to every other vertex so that i can use dijkstra's algorithm to find the shortest path. The problem is that when i do the calculation some overflow and create negative numbers. I was told if i mod each step it would stop the overflow vs mod the entire value , however neither are working. I'v tried starting with a long then casting to a int still get negatives. If someone could help me that be great!

public void setweights()

{

for(int row=0; row < 20 ;row++ )

{

for( int col=0 ; col < 20; col++)

{

// graph[row][col].setDistance(

int f = ( ((3751 * to.getRow() + 6539 * graph[row][col].getRow() ) % 1213 )* ((3751 * graph[row][col].getRow() + 6539 * to.getRow() ) %1213)

+ ((4567 * to.getCol() + 9673 * graph[row][col].getCol() ) % 1213) * (( 4567 * graph[row][col].getCol() + 9673 * to.getCol() )%1213)

)

+ 1 ;

//int j = (int) f;

System.out.println(f);

}

}

}

above was trying to mod each part to break it smaller but it gave me wird numbers

the original is as follows i tred modding the entire value

int f = ( (3751 * to.getRow() + 6539 * graph[row][col].getRow() ) * (3751 * graph[row][col].getRow() + 6539 * to.getRow() )

+ (4567 * to.getCol() + 9673 * graph[row][col].getCol() ) * ( 4567 * graph[row][col].getCol() + 9673 * to.getCol() )

) %1213

+ 1 ;

i was told i had to handle the overflow somehow any help would be much appreciated!

public void setweights()

{

for(int row=0; row < 20 ;row++ )

{

for( int col=0 ; col < 20; col++)

{

// graph[row][col].setDistanc

int f = ( ((3751 * to.getRow() + 6539 * graph[row][col].getRow() ) % 1213 )* ((3751 * graph[row][col].getRow() + 6539 * to.getRow() ) %1213)

+ ((4567 * to.getCol() + 9673 * graph[row][col].getCol() ) % 1213) * (( 4567 * graph[row][col].getCol() + 9673 * to.getCol() )%1213)

)

+ 1 ;

//int j = (int) f;

System.out.println(f);

}

}

}

above was trying to mod each part to break it smaller but it gave me wird numbers

the original is as follows i tred modding the entire value

int f = ( (3751 * to.getRow() + 6539 * graph[row][col].getRow() ) * (3751 * graph[row][col].getRow() + 6539 * to.getRow() )

+ (4567 * to.getCol() + 9673 * graph[row][col].getCol() ) * ( 4567 * graph[row][col].getCol() + 9673 * to.getCol() )

) %1213

+ 1 ;

i was told i had to handle the overflow somehow any help would be much appreciated!

6 Comments

Also, in a less programmatic sense, what is the weight function from one vertex of the graph to another? You can't arbitrarily insert a mod operation into the middle of a function without dramatically changing said function, so it sounds like you are heading down the wrong path altogether.

As an asside, I seem to recall that dijkstra's algorithm requires that you set the initial value of each node of the graph to "infinity". We don't have all of your code, but it's possible that some initialization operation iis messing you up.

ok, yeah sorry i didn't leave you much info here is the formula.

Vertex(r1,c1) to

Vertex(r2,c2) from

( (3751 * r1 + 6539 * r2 ) * (3751 * r2 + 6539 * r1 )

+ (4567 * c1 + 9673 * c2 ) * ( 4567 * c2 + 9673 * c1 )

) %1213

+ 1 ;

"to" is the first vertex

graph[row][col] are all others

I initially set the distances which is ok for dikstra's algorithm I just need to do this calculation without it going over the max integer value because it gioves me a negative value. And as we know negative values cause prblems with dijkstras algorithm.

Title | # Comments | Views | Activity |
---|---|---|---|

scores100 challenge | 3 | 68 | |

powerN challenge | 3 | 36 | |

json format text only | 4 | 50 | |

solarwind tftp server | 2 | 19 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**19** Experts available now in Live!