I have a written a program for Dijesktra algorithm;

But I encounter the run time error when the code returns "lp" value ...

Runtime check failure #2-Stack around the variable 'parent' is corrupted


please see the code

Could some one tell me that how to solve this prblem

thanks

// dijkstra.cpp : Defines the entry point for the console application.
//

#include "stdafx.h" // for console application ONLY
#include <string> // for string and substring
#include <sstream>//required for converting string into integer

#include <iostream>
#include <fstream>

#include <stdio.h>
#include <math.h>



using namespace std;

#define MAX_NODE 100 
#define MAX_PATH 50
#define MAX_ITER 100

double comrange;

int num_node;
float x[MAX_NODE];//we cannot declare it as int because, there is no overload function availble for pow(int,int) etc
float y[MAX_NODE];//as above

int cn[MAX_NODE][MAX_NODE];
int nexthop[MAX_NODE][MAX_NODE];
int numhop[MAX_NODE][MAX_NODE];

//void makenodeconf();//no need
void makecn();
void printcn();
void makertmat();
int spr(int path[MAX_PATH], int s, int d);
int findmin(int temp[MAX_PATH], int len);
int netcost(int u, int v);
void makertfile();

int main(int argc, char *argv[]) {
//	FILE *fp;
	fstream fp; //C++ style of declaring file stream pointer

	int i;

	float tn=0, tx=0, ty=0;
	int c=0;
	int r=0;
	size_t pos_from=0,pos_to=0,pos_end;

	if(argc<2) {
		printf("USAGE : %s [srcfile]\n", argv[0]);
		return -1;
	}

		fp.open(argv[1], ios::in);
		//fp.open("C:\\GridTopology_Simulation.txt",ios::in); //in the code, manually addressing the file path
			
		
	c=0;
	char str[2000];
	string coordinates;
	 
	if (fp.is_open())
	{
	while(!fp.eof()) {
		
		fp.getline(str,2000); //note the the total number of characters in the file, declared as 2000
		cout <<str<<endl;

		string strng(str);
		//r=fscanf(fp, "%d%d%d", &tn, &tx, &ty); // C style of reading
		
		for(int i=0;i<2;i++){
		if(i%2==0){//for the 1st index of the line
		pos_from = strng.find("(");    // position of "live" in str
		pos_end = strng.find(",");
		pos_to=(pos_end)-(pos_from);
		coordinates = strng.substr (pos_from+1,pos_to-1);   // get from "live" to the end
		stringstream ss(coordinates);
		ss >> tx;
		}
		else if(i%2==1){//for the next index
		pos_from = strng.find(",");    // position of "live" in str
		pos_end = strng.find(")");     //it ll get the index of ")"
		pos_to=(pos_end-5)-(pos_from); 
		// note that we have to subtract 5 from pos_end; for example the format looks like (900.0, 600.0, 0.0)...
		//Now we are interested in 600.0..whereas "0.0)" is fixed for the whole file document. Subtracting 5 from positon of ")"-->we will get last comma
		//and then we will read between 2 commas
		coordinates = strng.substr (pos_from+1,pos_to-1);   // get from "live" to the end
		stringstream ss(coordinates);
		ss >> ty;
		}
		}//end of for loop
		
		if(!strng.empty () ) {// who knows the file has empty lines at the end; if so then we need to make sure that x[c] and x[y] dont get that empty or zero input
			x[c] = tx;
			y[c] = ty;
			//cout <<endl<<x[c]<<"\t\t"<<y[c]<<endl;
			c++;
		}
		
		
		
	}//end of file
	}//end of if

	else
			 cout << "\n\nUnable to open file"<<endl<<endl;

	
	
	fp.close();
		
	
	

	num_node = c;
	//printf("num_node : %d\n", num_node);

	comrange=120;

//	makenodeconf();
	
	makecn();

	makertmat();

	makertfile();
}

/*void makenodeconf() {
	FILE *fp;
	int i;

	fp = fopen("nodeconf.tcl", "w");

	for(i=0;i<num_node;i++) {
		fprintf(fp, "$node_(%d) set X_ %lf\n", i, (double)x[i]);
		fprintf(fp, "$node_(%d) set Y_ %lf\n", i, (double)y[i]);
		fprintf(fp, "$node_(%d) set Z_ %lf\n", i, (double)0);
		fprintf(fp, "\n");
	}

	fclose(fp);
}*/

void makecn() {
	int i,j;
	double dist;
	float pow1=0,pow2=0, xcord=0, ycord=0;
	for(i=0;i<num_node;i++) {
		for(j=0;j<num_node;j++) {
			if(i==j) {
				cn[i][j] = 1;
				continue;
			}
			xcord=(x[i]-x[j]);
			ycord=(y[i]-y[j]);
			
			pow1=pow(xcord,2);
			pow2=pow(ycord,2);
			
			dist = sqrt(pow1+pow2);
			
				
			//printf("dist : %lf\n", dist);
			
			if(dist <= comrange) {
				cn[i][j] = 1;
			}
			else {
				cn[i][j] = 0;
			}
		}
	}

	//printcn();
}

void printcn() {
	int i,j;

	for(i=0;i<num_node;i++) {
		for(j=0;j<num_node;j++) {
			printf("\n this is CN metrix \t %d \n ", cn[i][j]);
		} 
		printf("\n");
	} 
}

void makertmat() {
	// based cn matrix
	
	int i,j;
	int path[MAX_PATH]={0,};
	int lp=0;
	//path[1]=0;      //its important because when the loop is 1st time run, path[1] (as its assigned in below statement) has garbage value which cause a run time error
	for(i=0;i<num_node;i++) {
		for(j=0;j<num_node;j++) {
			if(i==j) {
				continue;
			}
			
			lp = spr(path, i,j);
			cout<<"OKKK\n\n";
			printf("i %d, j %d, lp %d, path[0] %d, path[1] %d\n", i, j, lp, path[0], path[1]);

			// nexthop
			nexthop[i][j] = path[1];                   // here there was a run time error
			// numhop
			numhop[i][j] = lp-1;
		}
	}
}

int spr(int path[MAX_PATH], int s, int d) {
	int visited[MAX_NODE] = {0,};
	int distance[MAX_NODE] = {10000,};
	int parent[MAX_NODE] = {num_node+1,};

	int i,j,k;
	int temp[MAX_PATH];
	int lt;
	int lp;

	int h;
	int t,u,v;

	int c;

	for(i=0;i<MAX_NODE;i++) {
		distance[i]=10000;
		parent[i]=num_node+1;
		
	}
//cout<<i<<"\t\t"<<parent[i-1];

	distance[s] = 0;

	//printf("spr s:%d, d:%d\n", s,d);

	for(i=0;i<num_node-1;i++) {
//		for(k=0;k<MAX_PATH;k++) {
//			temp=0;
//		}
		lt=0;

		for(h=0;h<num_node;h++) {
			if( visited[h] == 0 ) {
				//printf("h %d\n", h);
				temp[lt++] = distance[h];
			}
			else {
				temp[lt++] = 10000;
			}
		}
//cout<<"OKKK\n\n";
		u=findmin(temp,lt);
		//t=u;
		if(u<0) {
			printf("error\n");
		}
//cout<<"OKKK\n\n";

		visited[u]=1;
		for(v=0;v<num_node;v++) {
			if(distance[u] + netcost(u,v) < distance[v]) {
				//printf("u %d, v %d\n", u, v);
				distance[v] = distance[u] + netcost(u,v);
				parent[v] = u;
			}
		}

	}//outer for loop
//cout<<"OKKK\n\n";

	path[0]=d;
	lp=1;
	c=0;

	while(path[0] != s) {
		c++;
		//cout<<c<<"\t\t1st okkkOKKK\n\n";
		if(c>MAX_ITER) {
			
			lp=0;
			//cout<<c<<"\t\tOKKK Insideeeeeee\n\n\t\tlp="<<lp<<endl;
////////////************************************************************/////			
			return lp; /// here error occured as run time error
///***********************************************************************////
			//cout<<c<<"\t\tRETURN OCCURED\n\n";
		}

		cout<<c<<"\t\tOuter OKKK\n\n";
		
		
		if(parent[path[0]] <= num_node) {
			
			for(k=0;k<lp;k++) {
				path[lp-k] = path[lp-k-1];
				
			}
			//printf("path[1] : %d\n", path[1]);
			path[0] = parent[path[1]];
			
			lp++;
			
		}
	}//end of while
	
	return lp;
}


int findmin(int temp[MAX_PATH], int len) {
	int i;
	int m;
	int mi=-1;
	
	if(len==0) {
		return -1;
	}

	m=10000000;
	for(i=0;i<len;i++) {
		if(temp[i]<=m) {
			m=temp[i];
			mi=i;
		}
	}

	return mi;
}


int netcost(int u, int v) {

	int i;
	int r=10000;

	if(cn[u][v]==1) {
	//	r=100-v;
		r=1;
	}

	return r;
}

void makertfile() {
	int i;
	int j;
	FILE *fp;
	
	fp=fopen("routefile", "w");
	for(i=0;i<num_node;i++) {
		for(j=0;j<num_node;j++) {
			if(i==j) {
				continue;
			}
			
			fprintf(fp, "%d %d %d %d\n", i, j, nexthop[i][j], numhop[i][j]);
		}
	}

	fclose(fp);
}

> int temp[MAX_PATH];
At line 224.

At line 250 onwards, you assume this has MAX_NODE elements

The only place that I can see where array parent might get written to outside its range is this bit in function spr()

for(v=0;v<num_node;v++) {
			if(distance[u] + netcost(u,v) < distance[v]) {
				//printf("u %d, v %d\n", u, v);
				distance[v] = distance[u] + netcost(u,v);
				parent[v] = u;

Is there any way that num_node can possibly be larger than MAX_NODE?

> int temp[MAX_PATH];
At line 224.

At line 250 onwards, you assume this has MAX_NODE elements

Dear
Thanks a lot.......you have solved my problem; it took me about one day but I was unable to figure it out.
Thanks once again

This article has been dead for over six months. Start a new discussion instead.