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

#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>

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)]);
	return(k);
}

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";
else
{
copq.rear=t;
copq.col[copq.rear]=i;
}
}


int main()
{


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

	cout<<"\n Enter number of jobs";
	cin>>track.n;
	n = track.n;
	track.head=track.rear=0;

	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";
	cin>>lower;
	cin>>upper;
	
	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)];
}

	track.col[track.head]=track.col[track.rear]=n;
	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";
i=0;
while(i<n)
{
	cout<<"\ts";
	j=i;
	while(j<F[ij_to_k(i, 2, 2)])
	{
		cout<<"\t"<<++j;
		
	}
	
	i=j;
}
}

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:
1.

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 article has been dead for over six months. Start a new discussion instead.