Hey guys, I have been working on this program for my entire semester. I got it down to do what I want I think... except when I compile it, I get no errors or warnings (using Dev) and when I execute it runs through half of it and it stops and gives me a error saying the program stopped responding.

I tried debuging it but I don't know what it's telling me when it sends me to a if loop. Anyone have any suggestions, the program is displayed below and the text file is attached.

#include<iostream> //File input/ouput include files
#include<fstream>
#include<iomanip>
#include<set>
#include<list>



using namespace std; //C++ standard libraries
const int NUMARCS = 16; //Need to use const ints for array declaration
const int NUMNODES = 8;
int i;
int main() //Main function
{
	ifstream readin("fstarin.txt", ios::in); //open input file
	ofstream readout("hw5out.txt", ios::out); //open output file
	if (!readin) {
		cerr << "File could not be opened" << endl; //Make sure file opens
		exit(1);
	}
	//declare arrays to be used
	int tail[NUMARCS+1], head[NUMARCS+1], cost[NUMARCS+1], cap[NUMARCS+1];
	//Initilize point[i] = 0... this will be a useful condition later
	int point[NUMNODES+2] = {0};
	int i = 1;
	/*This is a fairly concise loop to read the input file and assign
	the input stream to the arrays created. This same loop outputs the
	arrays as well. Note that setw() is for formatting output*/
	while (readin >> tail[i] >> head[i] >> cost[i] >> cap[i])
	i++;
	readout << setiosflags(ios::left) << setw(7) << "Arc #" << setw(7) << "Tail"<< setw(7)<< "Head"	<< setw(7)<< "Cost"	<< "Capacity" << endl;
	for (i = 1; i <= NUMARCS; i++) 
	{
		readout << setiosflags(ios::left) << setw(7) << i << setw(7) << tail[i]
		<< setw(7) << head[i]
		<< setw(7) << cost[i]
		<< cap[i] << endl;
	}
	/*Now I use a loop to assign the point vector to the first arc in the
	forward star having the same tail node. Note that nodes with no
	emanating arcs will still have point[i] = 0*/
	for (i = 1; i<= NUMARCS+1; i++) 
	{
		if (point[tail[i]] == 0) 
		{
			point[tail[i]] = i;
		}
	}
	//Now I clean up those nodes with no emanating arcs
	for (i = 1; i<=NUMNODES; i++) 
	{
		if (point[i] == 0) 
			{
				point[i] = point[i+1];
			}
	}
	/*Lastly, we can set the pointer for the n+1 node, we can do it this
	simply wlog becasue this condition will hold for all forward star
	representations*/
	point[NUMNODES+1] = NUMARCS +1;

	//Output the pointer vector
	readout << endl;
	readout << "The point vector is: [";
	for (i = 1; i <= NUMNODES+1; i++) 
	{
		readout << point[i] << " ";
	}
	readout << "]";
	readout << endl;
	readout << endl;
	/*This is the initialization phase of Dijkstra's: we need to construct the
	temporary and permenently labeled node sets. The Perm set is initially empty,
	the temporary initially contains all nodes. We then declare and initialize
	the label and predecessor vector*/
	//There are containers called sets with predefined operations that are useful
	//in this context
	set<int> Perm;
	set<int> Temp;
	set<int>::iterator it;
	for (i = 1; i <= NUMNODES; i++) 
	{

		Temp.insert(i);
	}
	int label[NUMNODES+1], pred[NUMNODES+1], lownode, lowlabel;
	for (i = 1; i <=NUMNODES; i++) 
	{ 
		label[i] = 1000; 
	}
	label[1] = 0;
	pred[1] = 0;
	/*We enter the main loop, checking that not all nodes are permanently labeled*/
	while (Perm.size() < NUMNODES) 
	{
		lownode = 0;
		lowlabel = 100000;
		/*The first loop now checks for the lowest temporary distance label. This is
		an easy, loop-based check*/
		for (it = Temp.begin(); it != Temp.end() ; it++) 
		{
			if (label[*it] < lowlabel) 
			{
				lowlabel = label[*it];
				lownode = *it;
			}
		}
		//Remove the node from the temp set, add it to the permanent set
		Temp.erase(lownode);
		Perm.insert (Perm.end(),lownode);
		/*Now, using the forward star, identify those arcs emanating from our newly
		permanently labeled noede and update distance labels and pred vector as
		appropriate*/
		for (i= point[lownode]; i < point[lownode+1]; i++) 
		{
			if (label[head[i]] > label[lownode] + cost[i]) 
			{
				label[head[i]] = label[lownode] + cost[i];
				pred[head[i]] = lownode;
			}
		}
	}
		//Output the distance labels and predecessor vector
		readout << "The optimal distance labels are:" << "[";
		for (i = 1; i <=NUMNODES; i++) 
		{
			readout << " " << label[i];
		}
	readout << "]" << endl << endl;
	readout << "The predecessor vector is:" << "[";
	for (i = 1; i <=NUMNODES; i++) 
	{
		readout << " " << pred[i];
	}
	readout << "]" << endl << endl;
	/*Now we can identify the shortest path from 1 to all. Use the list container
	as lists do not automatically sort the contents*/
	list<int> path;
	list<int>::iterator iter;
	for (i = 2; i <=NUMNODES; i++) 
	{
		readout << "The shortest path from node 1 to node " << i << " is: 1";
		int current = i;
		path.erase(path.begin(), path.end());
		while (pred[current] != 0 ) 
		{
			path.insert(path.begin(), current);
			current = pred[current];
		}
		for (iter = path.begin(); iter !=path.end(); iter++) 
		{
			readout << "-" << *iter;
		}
		readout << endl;
	}
	return 0;
}

here is the text, it's also attached
1 2 2 4
1 3 3 7
2 4 2 6
2 5 6 8
2 6 8 8
3 2 5 5
3 5 3 8
3 8 5 9
4 3 2 4
4 5 3 4
4 6 3 9
4 7 1 5
5 7 6 4
5 8 1 2
7 6 1 5
8 7 2 9

Recommended Answers

All 7 Replies

Your program is experiencing out-of-bounds errors. The arrays are allocated 17 elements numbered 0-16 and your program is attempting to write to elements 1-17. Element #17 does not exist.

Learn to count the C and C++ way -- with 0 as the base value. Your program is chuck full of buffer overruns and out-of-bound errors.

I thought i accounted for that though, by having i start at 1 in every itteration. I don't understand what I'm suppose to do to change it. I tried looking through the program and I don't have anything that seems that it wouldn't work.

I tried changing the const instead of 16 to 15, and the nodes from 8 to 7, and then vise versa up to 17, and 9, and still having the same thing happening...

When I try to debug it, it points to this line but I don't know what's wrong w/ it...

for (i = 1; i<= NUMARCS+1; i++) 
	{
		if (point[tail[i]] == 0) 
		{
			point[tail[i]] = i;
		}
	}

When I try to debug it, it points to this line but I don't know what's wrong w/ it...

for (i = 1; i<= NUMARCS+1; i++) 
	{
		if (point[tail[i]] == 0) 
		{
			point[tail[i]] = i;
		}
	}

try this

for (i = 0; i< NUMARCS+1; i++)

I did, I tried changing all the 1's to 0's also, that didn't help, then I tried leaving them at 0's and bring down the numbers of everything that didn't work tried bringing it up.. I honestly can't figure it out tried singling out stuff and same problem.

It isn't pointing at the for, it's pointing at the if, i tried changing that 0 to 1 also. I honestly can't think anymore spent about eight hours writing this today with all the errors and i can't get it to work

it's telling me it's unable to handle exception when it poitns to that if statement

Holy crap I solved it guys!!! Thank you sooooooooo much the program works!!!

All I had to do was take out the +1 on

for (i = 1; i< NUMARCS+1; i++)

and change it too

for (i = 0; i< NUMARCS; i++)

I can't thank you guys enough really honestly, I freaking love Daniweb!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.