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