Hey,
So I am having this problem with this code. I think the problem is that shortpath[0].distance is being set to 0, and so never going into the if statement of updatepaths() therefore messing up the whole program. But I don't know why it is being set to 0.
Here is the code:
//*****************************************************************************************
// This program finds the shortest path from one vertex of a 'dgraph' to all others.
// It uses: a 'Set' to keep track of the shortest path vertices;
// a table (of type Vertexinfo) that, for each vertex keeps track of its edges,
// where each edge goes (to which vertex) and each edge's weight
// - this information is supplied -;
// a final table (of type Shortpath) that keeps track of each vertex's overall
// weight (from the starting vertex) and how to get to it
// - this information must be calculated and is the program's goal -.
// filename: graph1.cpp
// Author: Kimberlie Davis
//*****************************************************************************************
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cctype>
#include "sets.cpp"
int const VERTICES = 5;
int const TOOLARGE = 30000;
using namespace std;
struct Pathinfo
{
int vertexto;
int weight;
};
struct Vertexinfo
{
int edgecount;
Pathinfo path[VERTICES - 1];
};
struct Shortpath
{
int distance;
int via;
};
class Paths
{
private:
Vertexinfo edgedata[VERTICES];
Shortpath shortpath[VERTICES];
Set done;
public:
void filldata(void);
void filldatafile(char []);
void printdata(void);
void initialize(int);
int findshortest(void);
void updatepaths(int);
void printpaths(int);
void calculate(int);
};
//--------------------------------------------------------------------------
// 'filldata' for each vertex, receives a count of the number of edges,
// then for each edge finds out where it goes (vertex to) and the weight.
//
// A problem exists in that the user names the vertices from 1 up, but
// they will be used as subscripts (which start at 0); so 1 is subtracted
// from the vertex number being input
//--------------------------------------------------------------------------
void
Paths::filldata ( )
{
int vertex, edge;
cout << "For each vertex first enter the number of edges to it\n";
cout << "then for each edge input the vertex it goes to and its weight\n\n";
for (vertex = 0; vertex < VERTICES; vertex++)
{
cout << " For vertex number " << vertex+1 << '\n';
cout << " How many edges : ";
cin >> edgedata[vertex].edgecount;
for (edge = 0; edge < edgedata[vertex].edgecount; edge++)
{
cout << " Edge number " << edge+1 << '\n';
cout << " To vertex # ";
cin >> edgedata[vertex].path[edge].vertexto;
edgedata[vertex].path[edge].vertexto--; // <---- turn into subscript
cout << " Weight ";
cin >> edgedata[vertex].path[edge].weight;
}
}
}
//--------------------------------------------------------------------------
// 'filldatafile' for each vertex, receives a count of the number of edges,
// then for each edge finds out where it goes (vertex to) and the weight.
// the data comes from a file, the filename is asked of the user
// A problem exists in that the user creates the file using vertices
// numbered from 1 up, but they will be used as subscripts (which start at 0)
// so 1 is subtracted from the vertex number being input
//--------------------------------------------------------------------------
void
Paths::filldatafile (char filename[])
{
int vertex, edge;
ifstream infile;
infile.open(filename);
if (!infile.fail())
{
for (vertex = 0; vertex < VERTICES; vertex++)
{
infile >> edgedata[vertex].edgecount;
for (edge = 0; edge < edgedata[vertex].edgecount; edge++)
{
infile >> edgedata[vertex].path[edge].vertexto;
edgedata[vertex].path[edge].vertexto--; // <---- turn into subscript
infile >> edgedata[vertex].path[edge].weight;
}
}
}
else
{
for (vertex = 0; vertex < VERTICES; vertex++)
edgedata[vertex].edgecount = 0;
}
}
//--------------------------------------------------------------------------
// 'printdata' displays the entered vertex information so the user can make
// sure the data is entered correctly. To compensate for the vertices
// being used as subscripts, 1 is added to the vertex display. 1 is also
// added to the edge for display since edge is also used as a subscript
//--------------------------------------------------------------------------
void
Paths::printdata ( )
{
int vertex, edge;
cout << "\nThe following data was input\n\n";
for (vertex = 0; vertex < VERTICES; vertex++)
{
cout << " Vertex number " << vertex+1 << " ";
cout << edgedata[vertex].edgecount <<" edges\n";
for (edge = 0; edge < edgedata[vertex].edgecount; edge++)
{
cout << " Edge number " << edge+1 ;
cout << " To vertex # " << edgedata[vertex].path[edge].vertexto+1;;
cout << " Weight " << edgedata[vertex].path[edge].weight << '\n';
}
cout << '\n';
}
}
//--------------------------------------------------------------------------
// 'initialize' takes the starting vertex and stores it as the the 'via'
// for each vertex. It also sets the distance to a very large number;
// except the starting vertex where the distance is set to 0
//--------------------------------------------------------------------------
void
Paths::initialize (int startnode)
{
int i;
for (i = 0; i < VERTICES; i++)
{
shortpath[i].distance = TOOLARGE;
shortpath[i].via = startnode;
}
shortpath[startnode].distance = 0;
}
//--------------------------------------------------------------------------
// 'findshortest' searches the distance/via table for the smallest weight
// of a vertex that hasn't yet been completed (i.e. not in the Set)
//--------------------------------------------------------------------------
int
Paths::findshortest ( )
{
int vertex, smalldist, smallvertex;
smalldist = TOOLARGE;
smallvertex = TOOLARGE;
for (vertex = 0; vertex < VERTICES; vertex++)
if (!done.in(vertex) && shortpath[vertex].distance < smalldist)
{
smalldist = shortpath[vertex].distance;
smallvertex = vertex;
}
return smallvertex;
}
//--------------------------------------------------------------------------
// 'updatepaths' uses the newest vertex which was added to the Set to modify
// the distances of the remaining vertices (if smaller)
// in addition to the newly added vertex, it uses the Set, the Vertexinfo
// and the Shortpath tables
//--------------------------------------------------------------------------
void
Paths::updatepaths(int value)
{
int total;
int subscript;
for(int i = 0; i < edgedata[value].edgecount; i++)
{
if(!done.in(edgedata[value].path[i].vertexto))
{
total = edgedata[value].path[i].weight + shortpath[value].distance;
if(total < shortpath[i].distance)
{
shortpath[i].distance = total;
shortpath[i].via = value;
}
}
}
}
//--------------------------------------------------------------------------
// 'calculate' initialized the Set done, adds the starting vertex to done,
// then performs a loop finding the next shortest path, adding it to the
// set, and updating the shortpath table
//--------------------------------------------------------------------------
void
Paths::calculate (int addnode)
{
int loop;
done.initialize();
done.add(addnode);
updatepaths (addnode);
for (loop = 1; loop < VERTICES; loop++)
{
addnode = findshortest( );
if (addnode != TOOLARGE)
{
done.add(addnode);
updatepaths(addnode);
}
}
}
//--------------------------------------------------------------------------
// 'printpaths' displays a table showing the starting vertex then every
// vertex, its final weight (distance) and how to get there (via)
// this last information is in the Shortpath table
//--------------------------------------------------------------------------
void
Paths::printpaths(int value)
{
cout << "Vertex: " << " " << "Distance: " << " " << "Via: " << endl;
for(int i = 0; i < 5; i++)
{
cout << i+1 << " " << shortpath[i].distance << " " << shortpath[i].via+1 << endl;
}
}
//------------------------- main routine -------------------------
int
main()
{
Paths findall;
int startvertex, addnode;
char response;
char file[25];
do
{
cout << "Is the data being input from a file (y/n) ? ";
cin >> response;
if (tolower(response) == 'y')
{
cin.get();
cout << "Please enter the filename : "<<flush;
cin.getline(file, 25);
findall.filldatafile(file);
}
else
findall.filldata();
findall.printdata();
cout << "Is the data correct (y/n) ? ";
cin >> response;
}
while (tolower(response) == 'n');
do
{
cout << "\nWhat is your starting vertex number? ";
cin >> startvertex;
addnode = startvertex - 1;
findall.initialize (addnode);
findall.calculate (addnode);
findall.printpaths (startvertex);
cout << "\nWould you like to see the distances starting from another vertex (y/n) ? ";
cin >> response;
}
while ( tolower(response) == 'y' );
system("pause");
return 0;
}