shorthest path-another way

Pandiani · #1 08-May-2004, 16:10

Shortest path algorithm:

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 (could be double as well)(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.

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

That's it for the algorithm.

I tried to implement it by myself and here's my shot

CPP / C++ / C 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();
}

But array distance is not update, I don't know why.
Few brains are clever then one. I hope you will see where I made mistake implementing algorithm showed above.
I think I manage to provide enough information about problem that I'm trying to solve. That is practicaly just c++ implementation of above algorithm.
I hope someone wil be able to help
Thanks in advance!

dsmith · #2 09-May-2004, 08:38

Hi Pandiani. That definitely is a complete post

.

If I get some spare time, I will look over your algorithm and code and see if I can see anything. It does intrigue me.

However, this is a pretty time-consuming problem that you have posted and you may not get timely replies or any replies as this is a voluntary endeavor.

I hope that this does not discourage you and that you will continue to visit these forums. Asking short and specific questions will generally always get you an answer and your knowledge of C++ would be a welcome addition around here.

Cheers,
d

Pandiani · #3 09-May-2004, 09:18

Yes, I realize that. I'm still begginer in C++ programming, but studying hard. And I thought a rasonable step forward would be to learn algorithms.
I've been programming in C++ for two-three months and realised that I have been playing all the time and not making any serious work.
I thought Graph theory is something that a little more experienced programmer
simply must know.
I cannot afford expensive courses and learning on my own, so I must wait that someone help me with issues I cannot deal with.
Thanks for replying.
In this particular thread I paste my approach so it could be easier to track my errors. From my point of view everything seems logical, but in programming.... thing are not always logical.
Anyway I would appreciate any help I can get.
Thanks for replying.
I hope you will be able to help

dsmith · #4 09-May-2004, 11:15

Not a problem, Pandiani. I can't speak for everyone here, but I am not a professional programmer, it is more of a hobby of mine. So there are lots of things that are new to me

Anyway, your code is well formatted, logical and implements a very interesting algorithm. That is why it intrigues me and I would love to be able to play with it for a bit and see if I can figure anything out. I just don't have a lot of free time lately and it may be several days before I can give it the attention that it needs.

Once again, I encourage you to stick around because I think that you could help all of us.

Talk at you later,
d

machinated · #5 09-May-2004, 11:20

wow pandiani you must be quite motivated! I've known c++ since high school (last 5 years or so) and i've never even done anything like this on my own. Don't get me wrong, i've done many programs like this but it was all school work. I've never wantingly done it. And forget about learning c++ at home! I woulda never done that! I am not motivated that easily!!!! Are there any specific foods I should eat to get that kind of motivation or waht??

Pandiani · #6 09-May-2004, 12:21

There is no specific food.
How about someone tell you that you're never be good c++ programmer?
You have two choices:
1. punch him right into nose
2. prove him that he was wrong

Max Payne · #7 09-May-2004, 20:51

Quote:

Originally Posted by Pandiani

There is no specific food.
How about someone tell you that you're never be good c++ programmer?
You have two choices:
1. punch him right into nose
2. prove him that he was wrong

I'll chose the second one!!

Pandiani, you rock! This is something that could motivate some of my friends and juniors who thinks c++ suck!

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
shortest path algorithm and file saving	Pandiani	C++ Forum	10	17-Jul-2006 11:46
[Tutorial] Standard I/O	aaroncohn	C Programming Language	20	27-Feb-2004 22:07