Ok, so i have an assignment due in 9 hours, its about computing the shortest paths from a vertix input by the user to all other vertices. The adjacency matrix is supplied from a text file, so I have done the following code:
(Some of it was given for me to begin with, the main functions were done by me:)
The final output should be to print all the paths from the base vertix supplied by the user to all others. The function that should be implemented is the sthPath and the other functions used in it.
Help Please!!

Edge class:

// File: Edge.h
// Definition of Edge class
/* _______________________________________________________________
An edge (u,v,w) existing between nodes (u) and (v) with weight (w) 
is modeled as a class (Edge).
__________________________________________________________________
*/

#ifndef EDGE_H
#define EDGE_H

typedef int weightType;		// weights are positive integers

class Edge
	   {
		public:
			int u;
			int v;
			weightType w;
			bool operator < (const Edge &e)
			{ return (w < e.w); }
			bool operator <= (const Edge &e)
			{ return (w <= e.w); }

	   }; // end of class Edge declaration
#endif // EDGE_H

Header file:

// File: Graphs.h
// Graph library header file
/*
______________________________________________________________________________________________

  This file describes a structure for a weighted undirected graph with a maximum of Vmax = 50 
  vertices and Emax = Vmax(Vmax-1)/2 edges. The verices are numbered 0,1,...V-1. The graph is
  assumed to be on a text file in the form of an adjacency matrix. The weights on the edges are
  assumed to be positive integers with zero weight indicating the absence of an edge. 
  An edge (u,v,w) existing between nodes (u) and (v) with weight (w) is modeled as a class
  (Edge). When loaded from the text file, the weights are stored in a  2-D 
  array (AdjMatrix) representing the adjacency matrix. Another  array (edges) stores 
  the non-zero edges in the graph. The functions declared here are needed to implement the
  Dijkstra's Algorithm to compute the shortest paths from a given source node to all other
  nodes in the graph.
_______________________________________________________________________________________________	
*/

#ifndef GRAPHS_H
#define GRAPHS_H
#include <string>
#include "Edge.h"
using namespace std;

const int Vmax = 50;					// Maximum number of vertices
const int Emax = Vmax*(Vmax-1)/2;		// Maximum number of edges
class Graphs
{
   public:
	
//_____________________________________
	// Member Functions
	// Class Constructor & Destructor
	Graphs();
	~Graphs();

// Function Prototypes___________________

	char Vname(const int s) const;		// Map vertex number to a name (character)
	void getGraph(string fname);		// Get Graph from text File (fname)
	void dispGraph() const;				// Display Ajacency Matrix
	int  No_of_Verices() const;			// Get number of vertices (V)
	int  No_of_Edges() const;			// Get Number of Non-zero edges (E)
	void dispEdges() const;				// Display Graph edges
	void shPath(int s);					// Shortest paths from node (s)

//______________________________________________________________________________________________


   private:
	   
	   int V, E;							// No.of vertices (V) and edges (E) 
	   weightType AdjMatrix[Vmax][Vmax];	// Adjacency Matrix
	   Edge edges[Emax];					// Array of non-zero edges
	   weightType distance[Vmax];			// Distance array for shortest paths
	   int via[Vmax];						// Via array for shortest paths
	   bool processed[Vmax];				// processed array for shortest paths

	   bool prcd();
	   int directDistance(int i,int j);
	   bool isAdjacent(int i,int j);
	   int getClosest(int s);
	   void getEdges();						// Get Non-Zero edges from adjacency matrix  
	   void printEdge(Edge e) const;		// Output an edge (e)
	   void printPath(int s,int i) const;	// Print path from source (s) to destination (i)
};
#endif // GRAPHS_H
#include "Graphs.cpp"

Main cpp file:

// FILE: graphs.cpp
// Graph Library Implementation File

#include <fstream>		// For reading file from disk
#include <iostream>
#include <string>		// For file name
#include <iomanip>
#include "Edge.h"		// Deinition of an Edge

using namespace std;

// Constructor
Graphs::Graphs()
{
	E = V = 0;
	//Removed variable called order (was =0)
}

// Destructor
Graphs::~Graphs()
{
}


// Map vertex number (0,1,2,..) to (A,B,C,..)
char Graphs::Vname(const int s) const
{
	return char(s+65);
}

// Get Graph from text File (file name is stored in string fname)
// Graph is stored in adjacency matrix
void Graphs::getGraph(string fname)		
{
   // Local data ...
	weightType wi;
	int i,m,r,c;
	ifstream source;

	source.open(fname.c_str()); 
	source >> V;	// Read no. of verices (V)
	m = V*V;		// Total Number of weights in file
	
	// Convert from a 1-D file of size m weights 
	// to a 2-D Adjacency Matrix of V rows and V columns
	int temp1;

	for (i = 0; i < 256; i++)
	{

		source >> temp1;
		r = i / V;
		c = i % V;
		AdjMatrix[r][c]=temp1;
		// get a weight from file
		// compute row(r) and column(c) 
		// put weight in adjacency matrix at [r][c]
	}
	source.close();
	getEdges();
	// close file
	// Get graph edges
	
}

// Display Adjacency Matrix
void Graphs::dispGraph() const
{
	int i,j;
	cout<<"Adjacency Matrix\n";
	for(i=0; i<V; i++)
	{
		for(j=0; j<V; j++)
			cout<< setw(3)<< AdjMatrix[i][j] << " ";
		cout<< endl;
	}
}

// Get Non-Zero edges from adjacency matrix
// and store them in array edges[]. 
void Graphs::getEdges()			
{
	int r , c;
	int i = 0;
	weightType weight;

	// Only examine weights above the diagonal 
	for (r = 0; r <= V-2; r++)
		for (c = r+1; c <= V-1; c++)
		{
			weight = AdjMatrix[r][c];
			if (weight > 0)
			{
				// save (r,c,weight) in edges[i]
				edges[i].u = r;
				edges[i].v = c;
				edges[i].w = weight;
				i++;
			}
		}

	E = i;		// Number of non-zero edges
	
}

// Get number of vertices (V)	
int Graphs::No_of_Verices() const 				
{
	return V;
}

// Get Number of Non-zero edges (E)
int Graphs::No_of_Edges() const 					
{
	return E;
}

// Output an edge (e): Vertex names and weight
void Graphs::printEdge(Edge e) const 			
{
	cout << Vname(e.u) << " " << Vname(e.v) << " " << e.w << endl;
}

// Display Graph Edges
void Graphs::dispEdges() const
{
	cout<<"Graph Edges\n";
	for (int i = 0; i < E; i++) 
		printEdge(edges[i]);
}

// Shortest paths from node s
// uses Dijkstra's Algorithm
void Graphs::shPath(int s)
{
	falsify();
	for(int k=0;k<V;k++)
		cout<<processed[k]<<endl;
	processed[s]=true;
	while(prcd()==false)
	{

		int j=getClosest(s);
		processed[j]=true;
		cout<<j<<"processed"<<endl;
		for(int i=0;i<V;i++)
		{
			if(processed[i]==true || isAdjacent(i,j)==false)
				continue;
			int new_distance = distance[j]+ directDistance(i,j);
			if(new_distance < distance[i])
			{
				distance[i]=new_distance;
				via[i]=j;
			}
		}
		for(int p=0;p<V;p++)
		{
			cout<<processed[p];
		}
		system("pause");
	}
	//printPath(s,5);
	//printing
		/*for(int i=0;i<V;i++)
		{
			if(i==s)
				continue;
			printPath(s,i);
		}*/

}
//function to get closest vertix adjacent to another
void Graphs::falsify()
{
	for(int i=0;i<V;i++)
	{
		processed[i]=false;
	}
}
bool Graphs::prcd()
{
	//function to check if all vertices proces or not yet
	for(int i=0;i<V;i++)
	{
		if(processed[i]==false)
			return false;
	}
	return true;
}
int Graphs::getClosest(int s)
{	//function to get closest adjacent vertix to another
	int j=-1;
	int temp_weight=9999;
	for(int x=0;x<V;x++)
		{
		if(processed[x]==true) continue;
		for(int k=0;k<E;k++)
			{
			if( (edges[k].u==s && edges[k].v==x) || (edges[k].u==x && edges[k].v==s) )
				{
				if(j==-1 || edges[k].w<temp_weight)
					{
					if(x==edges[k].u)
						j=edges[k].u;
					else
						j=edges[k].v;
					temp_weight=edges[k].w;
					}
				}
			}
		}
	return j;
}

// Print path (vertex names) from source (s) to destination (i)
int Graphs::directDistance(int i,int j)
{	//function to get direct distance from two nodes
	for(int k=0;k<E;k++)
	{
		if((edges[k].u==i &&edges[k].v==j) || (edges[k].u==j &&edges[k].v==i))
			return edges[k].w;
	}
	return 0;
}
bool Graphs::isAdjacent(int i,int j)
{	//function to check if two vertices are adjacent 
	for(int k=0;k<E;k++)
	{
		if((edges[k].u==i &&edges[k].v==j) || (edges[k].u==j &&edges[k].v==i))
			return true;
	}
	return false;
}
void Graphs::printPath(int s, int i) const
{
	if (i == s) cout << Vname(s);
	else
	{	printPath(s,via[i]);  cout << Vname(i);	}

	// Implement the function here
}

Recommended Answers

All 6 Replies

So what is the problem? Are there compiler errors? Does it crash? Do you get the wrong result?

I suggest hard coding a simple input that you can compute the entire algorithm by hand. Then you can check your programs state every step of the way.

i have done, the problem is it doesnt save the correct paths, and not all paths are computed. Ive traced some of it, for some base numbers few vertices are left unprocessed!!

What was your example graph? What is your hand computed solution? What is the programs computed solution?

ok, my example graph is:
16 0 46 46 54 85 37 45 57 80 85 0 42 26 53 79 68 46 0 83 63 29 35 60 0 0 71 24 33 84 83 34 49 46 83 0 84 43 85 55 68 44 44 80 57 82 47 59 45 54 63 84 0 53 90 86 70 77 30 0 72 60 95 21 34 85 29 43 53 0 37 60 44 0 20 69 31 75 27 0 67 37 35 85 90 37 0 85 0 82 36 43 90 81 45 93 0 45 60 55 86 60 85 0 40 38 72 23 96 0 27 73 28 57 0 68 70 44 0 40 0 0 23 66 80 38 22 83 98 80 0 44 77 0 82 38 0 0 94 76 48 33 36 0 44 85 71 44 30 20 36 72 23 94 0 90 63 64 67 91 84 0 24 80 0 69 43 23 66 76 90 0 22 25 32 46 85 42 33 57 72 31 90 96 80 48 63 22 0 71 0 74 71 26 84 82 60 75 81 0 38 33 64 25 71 0 32 23 0 53 83 47 95 27 45 27 22 36 67 32 0 32 0 0 65 79 34 59 21 0 93 73 83 0 91 46 74 23 0 0 78 68 49 45 34 67 0 28 98 44 84 85 71 0 65 78 0

it is read and converted in a 2d graph 16x16

My suggestion was to make a graph that you can sanely do the computations by hand. Maybe a graph with 5 nodes or so? If you don't know every step of the solution, your implementation will be almost impossible to debug.

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.