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

But I don't know why it is being set to

> Did you actually write this code yourself?

> If yes, you could try using a debugger

> BTW, Avoid the use of system("PAUSE"); (look at this excellent information written by WaltP :))

I wrote some of it. I did use a debugger, and still couldn't figure it out. I got it down to shortpath[0] is being set to 0 in the updatepaths() method though.

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