Thread: shortest path problems

i have a shortest path algorithm from my c++ book, but there are some problems with my implementation.

for one thing, i don't see how it will expand the search to further vertices after it gets the set of "neighbors" from the source vertex. (i believe i should be changing the source variable to something so that it doesn't keep picking the same neighbors.

neighbors returns a set of the vertex numbers that have an edge between source and neighbor.

if there are any further questions about the code, i'll try and answer them, but i'm kinda lost right now.

Code:

void shortest(graph<string> g, int source)
{
	int maximum = g.max();	//number of possible vertices in the graph
	vector<int> distance(g.size());
	vector<int> predecessor(g.size());
	string temp3;
	int next=0;
	int min=0;
	int min_vertex = 0;
	int sum=0;
	int v=0;

//step 1: fill distance array with -1 except for source, which is 0
	for (int i=0;i<g.size();i++)
	{
		distance[i] = -1;
	}
	distance[source] = 0;
//step 2: initialize set of vertices to empty set
	set<int> allowed_vertices;
//step 3:
	//3a.: next is the closest vertex to source which isn't in allowed_vertices set yet
	for (int allowed_size=1; allowed_size<=g.size(); ++allowed_size)
	{
		set<int> closest = g.neighbors(source); //set of all neighbors to source, 
        //the above is the part that finds the connected vertices and the part that i think might have to change the parameter to neighbor?

		min= g.is_edge(source, *closest.begin()); //is_edge returns an int, if the value is -1 the path isn't possible
		min_vertex=*closest.begin();
		for (set<int>::iterator it = closest.begin();it !=closest.end(); it++)
		{
			if (g.is_edge(source, *it)<min && g.is_edge(source, *it)!= 0)
			{
				if (allowed_vertices.count(*it)==0)
				{
					min=g.is_edge(source, *it);
					min_vertex=*it;
				}
			}
		}

		next=min_vertex;			//setting closest neighboring vertex
	//3b.: add next to allowed_vertices
		allowed_vertices.insert(next);

	//3c.: revise distance array so next appears on permitted path
		for (v=0;v < g.size(); ++v)
		{
			if ((allowed_vertices.count(v) == 0) && (g.is_edge(next, v)!=-1))
			{
				sum = distance[next]+g.is_edge(next, v);
//				if (sum < distance[next])
				
					distance[v] = sum;
					predecessor[v] = next;
				
			}
		}
	}
	//4.: output values in distance array

	//	testing
	cout<<"here are the distance vector values:" <<endl;
	for (int zz=0;zz<distance.size();zz++)
	{
		cout<<distance[zz] <<" ";
	}
	cout<<endl;
	cout<<"here are the predecessor vertex values:" <<endl;
	for (int zzz=0;zzz<predecessor.size();zzz++)
	{
		cout<<predecessor[zzz] <<" ";
	}
	cout<<endl;
	system("PAUSE");
	//	/testing

	int vertex_on_path = v;
	cout<<vertex_on_path <<endl;
	while (vertex_on_path!= source)
	{
		vertex_on_path = predecessor[vertex_on_path];
		g.label_vertex(vertex_on_path, temp3);	//error on this line
		cout<<temp3 <<endl;
	}
}

Go to the publishers web site and see if there are any errata's or "fixes" for the book.
Send an email to the author.
If this is a course book, ask your instructor.

gg

Without seeing the algorithm that your book proposes, its kinda hard to figure out exactly how your code is supposed to work to calculate the shortest distance. The techniques that I've use to find shortest distance paths are pretty different than this. Could you post the algorithm?

ok, here's the pseudocode straight from the book:

input. a directed graph with positive, integer edge weights and n vertices. one of the vertices, called start, is specified as the start vertex.

output. a list of the shortest distances from the start vertex to every other vertex in the graph.

the algorithm uses an array of n integers (called distance) and a set of vertices (called allowed_vertices). the variables v, allowed_size, and sum are local integer variables. there is some special value (-1) that we can place in the distance array to indicate an infinite distane (which means there is no path).

Step 1. initialize the distance array to contain all -1, except distance[start], which is set to zero.

Step 2. initialize the set of allowed vertices to be the empty set.

Step 3. Compute the complete distance array:

Code:

for (allowed_size = 1; allowed_size < n; ++allowed_size)
{
     // at this point, allowed_vertices contains allowed_size - 1 vertices, which are the 
     // allowed_size - 1 closest vertices to the start vertex.  Also, for each vertex v, distance[v] 
     // is the shortest distance from the start vertex to vertex v, provided that we are 
     // considering only permitted paths (i.e., paths where each vertex except the final vertex 
     // must be in allowed_vertices).

Step 3a. Let next be the closest vertex to the start vertex, which is not yet in the set of allowed vertices (if several vertices are equally close, then you may choose next to be any of them).
Step 3b. Add the vertex next to the set allowed_vertices.
Step 3c. Revise the distance array so that the new vertex (next) may appear on permitted paths:

Code:

     for (v = 0;v <  n; ++v)
     {
          if ((v is not an allowed vertex) and (there is an edge from next to v))
          {
               sum = distance[next] + (weight of the edge from next to v);
               if (sum < distance[v])
                    distance[v] = sum;
          }
      }
}

Step 4. Output the values in the distance array. (Each distance[v] is the shortest distance from the start vertex to vertex v.)

=========================

then, a couple pages later it said to update predecessor[v] with:

Code:

predecessor[v]=next;

after the assignment of:

Code:

distance[v] = sum;

Okay, I think I've figured out what the problem is, the pseudocode from the book is a little confusing. Basically, you don't want to be using the neighbors function for your graph to figure out the closest. Instead use your distance array. Loop through the distance array to find the closest vertice (the smallest value) that is not -1 and that is not already in allowed-vertices. This will be your next. So you use your own data to find the next closest, and this isn't always going to be directly connected to your source by an edge. The first time through the loop next will be your source since all others will be -1.

There might be other problems with the code, but that should at least solve the confusion you were having!

isn't the distance array filled after choosing next?

i believe that i'm supposed to get the new distance after finding next, but i could (probably) be wrong

Okay, here is an example of how I interpret the pseudocode. Say I have this graph of four points and the edges connecting them with distances:

Code:

   (2)
 2 / \ 1
  /   \
(1)   (3)
  \   /
 3 \ / 7
   (0)

Okay, lets make point 0 the source. Then we have the distance array which after being initialized looks like this:

distance[0]=0, distance[1]=-1, distance[2]=-1, distance[3]=-1

And allowed vertices starts off as being empty.

Now we do a loop that adds one vertice to allowed-vertices at a time until we hit the max, which in this case is 4. The vertice we enter is the one closest to the source but that is not in allowed-vertices yet.

Okay, first time through, we loop through the distance array looking for the shortest distance that is not -1 and that is not in allowed-vertices yet. Well they are all -1 except for distance[0] which is zero, so this is the shortest distance. And vertice zero is not in allowed-vertices yet, so vertice zero is our first next. Add vertice zero to allowed-vertices. Now cycle through all of the edges that next is connected to and update the distance of these vertices IF the distance is smaller than what its previous was. Vertice zero is connected to 1 and 3. Updating them makes distance[1]=3 and distance[3]=7. So now your distance array looks like this:

distance[0]=0, distance[1]=3, distance[2]=-1, distance[3]=7

Done with first time through loop. Now loop through distance array again looking for smallest distance. Distance[0] is the smallest, but vertice zero is in allowed-vertices, so ignore it. The next smallest is distance[1] at 3 and vertice one isn't in allowed-vertices so this is your next - add to allowed-vertices. Cycle through edges again updating vertice distances. Vertice two now becomes distance of five (distance[1]+edge distance to 2), but don't change vertice zero distance since its current distance of zero is smaller than the calculated distance of 6 (distance[1]+edge distance to zero). Distance array now looks like this:

distance[0]=0, distance[1]=3, distance[2]=5, distance[3]=7

Third time through loop. The next smallest amount in your distance array that isn't in allowed-vertices is vertice 2, so this is your next, add to allowed-vertices. Loop through edges updating it. The current distance for vertice one is better than the new calculated so don't change it, but the new calculated sum distance of 6 is better than the old distance to 3 which is currently 7, so change it to 6. Distance array now looks like this:

distance[0]=0, distance[1]=3, distance[2]=5, distance[3]=6

Last time through loop, only one left that hasn't been used is vertice 3, so this is your next. Cycling through the edges gives nothing but values that are greater than their old values, so don't change anything. Your final distance array with the correct distance to each point from point zero is:

distance[0]=0, distance[1]=3, distance[2]=5, distance[3]=6

Thats the gist of the algorithm, its easy enough to add in other things such as the previous array and printing the answer.

Hope this helps!

I tried to implement this interesting algorithm without using STL
and having some difficulties:

Code:

#include <iostream>
#include <limits>
using namespace std;

class Graph
{
	int size;
	double** adjmatrix;
	double* distance;
	int* predecessor;
	int *allowed_vertices;
	int find_min(double *);
	
public:
	Graph(int);
	~Graph();
	void load_adjmatrix();
	void show_adjmatrix();
	void shortest_path(int);
	void print_path();
	void show_distance();
};

Graph::Graph(int siz):size(siz)
{
	adjmatrix=new double*[size];
	distance =new double[size];
	predecessor=new int[size];
	allowed_vertices=new int[size];
	for(int i=0;i<size;i++)
	{
		distance[i]=-1;
		predecessor[i]=-1;
		allowed_vertices[i]=-1;
		adjmatrix[i]=new double[size];
	}
	for(i=0;i<size;i++)
		for(int j=0;j<size;j++)
		{
			adjmatrix[i][j]=0;
		}

	//load_adjmatrix();
		
}
Graph::~Graph()
{
	for(int i=0;i<size;i++)
	{
		delete adjmatrix[i];
	}
	delete [] adjmatrix;
	delete [] distance;
	delete [] predecessor;
}

void Graph::load_adjmatrix()
{
	//int node_number;
	double cost;
	char answer;
	for(int i=0;i<size;i++)
		for(int j=0;j<size;j++)
		{
			if((i!=j)&& adjmatrix[i][j] ==0)
			{
				cout<<"Is there a connection between node "<<i<<" and node "<<j<<"?";
				cout<<endl<<"Your answer (y for yes, any other key for no): ";
				cin>>answer;
				if(answer=='y' || answer=='Y')
				{
					while(1)
					{
						cout<<"Enter cost (distance-must be positive): ";
						cin>>cost;
						if(cin.good())
							break;
						else
						{
							cin.clear();
							cin.ignore(numeric_limits<int>::max(), '\n');
							cout << "\nInput Invalid. Please Try Again: "<<flush;
						}
					}
					adjmatrix[i][j]=adjmatrix[j][i]=cost;
				}
				else
					adjmatrix[i][j]=adjmatrix[j][i]=-1;
			}
			//cout<<endl;

		}
}

void Graph::show_adjmatrix()
{
	for(int i=0;i<size;i++,cout<<endl)
		for(int j=0;j<size;j++)
			cout<<adjmatrix[i][j]<<" ";

}

void Graph::shortest_path(int source)
{
	int next=0;
	//double min;
	int min_vertex = 0;
	double sum=0;
	int v=0;
	distance[source]=0;find_min(distance);

	for(int allowed_size=1;allowed_size<=size;allowed_size++)
	{	
		next=find_min(distance);
		allowed_vertices[allowed_size-1]=next;
		for(int i=0;i<size;i++)
			if (adjmatrix[next][i]!=-1)
          {
               sum = distance[next] + adjmatrix[next][i];
               if (sum < distance[i])
			   {
                    distance[i] = sum;
					predecessor[i] = next;
			   }
          }

	}
		
}
void Graph::show_distance()
{
	for(int i=0;i<size;i++)
		cout<<distance[i]<<" ";
}
int Graph::find_min(double *array)
{
	double min=0;
	int index=0;
	for(int i=0;i<size;i++)
		if(array[i]<min && array[i] !=-1)
		{
			for(int j=0;j<size;j++)
				if(i!=allowed_vertices[j])
				{
					min=array[i];
					index=i;
				}
		}
	return index;

}
int main()
{
	Graph obj(5);
	obj.show_adjmatrix();
	obj.load_adjmatrix();
	//obj.show_adjmatrix();
	obj.shortest_path(0);
	obj.show_distance();
}

Distance array is not update, but I cannot figure out way.
Please help