Can someone go through the following code whic generates shortest path for randomly generated processes. My code is generating a segmentation error when I run it, and I am unable to locate the bug.

//This program implements the O(n) algorithm for finding shortest path for randomly generated processing times


struct indexq{
	float *col;
	int head, rear, n;

float myrand(int lower, int upper)

	return (lower + rand() % (upper-lower+1));

int  ij_to_k(int i, int j, int n)
  return i*n+j;

float costij(float *arr, int k, int l,  int n)// function to compute cost of path from i to j
int s=1;
return((arr[ij_to_k(n, 2, 2)]-arr[ij_to_k(k, 2, 2)])*(s+arr[ij_to_k(l,1, 2)]-arr[ij_to_k(k, 1, 2)]));

float compf(float *sum,int i, int n)// function to compute f(i)= (W[n]-W[i])
	float k = (sum[ij_to_k(n, 2, 2)] - sum[ij_to_k(i, 2, 2)]);

float compv( int k, int l, float *P, float *F)//function to compute v=(F(k)-F(l))/(P[l]-P[k])
	return ( (F[ij_to_k(k, 1, 2)] - F[ij_to_k(l, 1, 2)])/(P[ij_to_k(l, 1, 2)]-P[ij_to_k(k, 1, 2)]));

void add(indexq &copq, int i, int n)
int t;
t = (copq.rear+1)%n;
if(t == copq.head)
cout<<"\nQueue Overflow\n";

int main()

indexq track;
float *pw, *PS;
int n, i=0, j=0;
float *F;
int upper, lower;

	cout<<"\n Enter number of jobs";
	n = track.n;

	pw = new float[n*2+2];
	PS = new float[n*2+2];
	F  = new float[n*2+2];	
//	cout<<"\n Enter processing times and their corresponding weights";
	cout<<"\n Enter lower and upper value to generate random processing times";
	pw[ij_to_k(0, 1, 2)]=0; pw[ij_to_k(0, 2, 2)]=0;

for(i=1; i<=n ;i++)
{	pw[ij_to_k(i, 1, 2)]= myrand(lower, upper);
	pw[ij_to_k(i, 2, 2)]=1;


	cout<<"\n\nPartial sums of processing times and weights are:\n ";
	PS[ij_to_k(0, 1, 2)]= 0; PS[ij_to_k(0, 2,2)]=0;

for(i=1 ; i<=n ; i++)//calculating partial sums of weights and processing times

	PS[ij_to_k(i, 1, 2)]= PS[ij_to_k(i-1, 1, 2)]+pw[ij_to_k(i, 1, 2)]; PS[ij_to_k(i, 2, 2)] = PS[ij_to_k(i-1, 2, 2)]+pw[ij_to_k(i, 2, 2)];
	cout<<"\n"<<PS[ij_to_k(i, 1, 2)]<<"\t"<<PS[ij_to_k(i, 2, 2)];

	F[ij_to_k(n, 1, 2)]=0; F[ij_to_k(n, 2, 2)]=0;

	cout<<"\n Minimum values in each row and column in which it is minimum";
//code to find the shortest path 
//First while loop deletes head of the queue until it satisfies the condition: head(Q)!=tail(Q) and f(i)>=v(next(head(Q)), head(Q)) 
//Second while loop deletes the tail of the queue if it satisfies the condition: head(Q)!=tail(Q) and v(i, tail(Q)) <= v(tail(Q), previous(tail(Q))

for( i = n-1; i>=0; i--)
	int temp= track.head+1;	
	while (track.col[track.head] != track.col[track.rear] && compf(PS,  i, n) >= compv( track.col[temp], track.col[track.head], PS, F))
	track.head = (track.head + 1)%n;
	float j = track.col[track.head];
	F[ij_to_k(i, 1, 2)] = costij(PS, i, j, n) + F[ij_to_k(j, 1, 2)];
	F[ij_to_k(i, 2, 2)] = j;
	int temp2 = track.rear-1;
	while(track.col[track.head] != track.col[track.rear] && compv(i, track.col[track.rear], PS, F) <= compv(track.col[track.rear], track.col[temp2], PS, F))
		track.rear = (track.rear-1)%n;
	add(track, i, n);
	cout<<"\n"<<F[ij_to_k(i, 1, 2)]<<"\t"<<F[ij_to_k(i, 2, 2)];
	cout<<"\n The schedule is\n";
	while(j<F[ij_to_k(i, 2, 2)])
8 Years
Discussion Span
Last Post by Cybulski

What input are you using when you get the segmentationfault? Because I ran the code and it didn't crash...
Two things I did notice:

pw = new float[n*2+2];
    PS = new float[n*2+2];
    F  = new float[n*2+2];

You never delete the memory you allocated => Memoryleak

2. float compv( int k, int l, float *P, float *F) If you call all your vars 'k','l','f' etc, it's almost impossible for other people to understand what you are trying to do. You should use meaningful names for variables; if P is an array of persons (for example), just call it float * PersonArray


If you using C++ (you are posting in C++ forum) you should take advantage of STL library which is part of language now. You should almost always use STL containers and avoid C-style arrays.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.