Finding shortest path!

[Oswld]

So this is driving me crazy. I'm coding the Dijskra algorithm to find the shortest path on a graph from a vertix v to a vertix nv and It's just not working, I hope someone can explain to me whats wrong and guide me on how to solve it. I know where the error is originating but i can't think of how to fix it.

This is the function that returns a pointer to an object of type Vertex.

Vertex* Dijkstra(Graph& g, int v, int nv)
{
	if(!g.is_in(v)) throw 2;		//Check if v is inside the graph
	if(!g.is_in(nv)) throw 2;

	int i=0,vlabel=0;
	int ulabel=9999;				

	Vertex* holder =new Vertex(v);	//Holder will be returned and will contain the shortests path
	
	PriorityQueue<Vertex*> pq;		//Priority Queue

	while(i<g.get_list().size())           //Fill PQ with Vertices in g
	{ 
		if(g.get_vertex(i)->getID() == v) pq.insertItem(vlabel,g.get_vertex(i)); //When v is found insert in pq with key =0
		else pq.insertItem(ulabel,g.get_vertex(i));
		
		i++;
	}
	
	while(!pq.isEmpty())
	{
		Vertex* cloud = pq.min_element();		//Set a vertex cloud to hold vertex with key 0
		vlabel = pq.min_key();					//Set label to key
		pq.remove_min();

		for(int m = 0; m < cloud->getOutEdges().size(); m++)	//While we havent looked at all the outward edges of cloud.
		{
			int templ = pq.find(cloud->get_out(m)->geteVertP());
			int tempk = pq.get_key(pq.find(cloud->get_out(m)->geteVertP()));

			if(cloud->get_out(m)->geteVertP()->getID() == nv )					// if we find nv is an outward edge, get its weight, insert it
			{																	// to the outward edges vector of cloud and return
				Edge* edge = new Edge(holder,pq.min_element(),pq.min_key()); 
				holder->getOutEdges().push_back(edge); 
				return holder;
			} 
																																												
			else if(vlabel + cloud->get_out(m)->getWeight() < tempk)
			{
				pq.decrease_key(templ, tempk-cloud->get_out(m)->getWeight());
			}
		}
		Edge* edge = new Edge(holder,pq.min_element(),pq.min_key());

		holder->getOutEdges().push_back(edge);
	
	}
		
	return holder;

}	

Now i know the error originates at this point

cloud->getOutEdges().size()

Also, the error that im getting is an Access Violation reading location.

Could it have something to do with the priority Queue i'm using? Or is my syntax just wrong?

[ne555]

> Or is my syntax just wrong?
Then it would not compile.
However, things like if(cloud->get_out(m)->geteVertP()->getID() == nv ) obfuscate the code.

By the way
_ if we find nv is an outward edge,
___ get its weight,
___ insert it to the outward edges vector of cloud
_ and return
is incorrect. You found one path, no the minimum path

[Oswld]

I see what you mean on the path statement. I didn't think of it like that.
And I though about that, so I tested it using this

int main()
{
   PriorityQueue<Vertex*> pq;

	int x =32;

	Vertex* cloud= new Vertex(x);

	pq.insertItem(x,cloud);

	Vertex* c = pq.min_element(); 

	cout << c->getID();
{

I still get the same error with this. Any idea what causes this? Would it help to look at the PriorityQueue class, or at least the functions that it uses in this case?

Just to clarify: The Vertex class takes an int which becomes the vertex id
and getID() just returns the id.

[ne555]

Good, that's quite small to look at.
Yes, post those functions

[Oswld]

Ok the basic stuff that im using for what i posted is this

template<typename ElemType>
class PriorityQueue {
public: 

	PriorityQueue(int size = DEF_SIZE) : T(size) {}
	
	void insertItem(const int k, const ElemType& e) { T.insert(Item(k, e)); } //Insert to the PQ

	const ElemType& min_element() //Return the element with the lowest key
	{
		if(T.is_empty()) throw 3;
		return T.min().get_elem();
	}
        protected: typedef Item<ElemType> Item;
		   typedef PQComp<ElemType> PQComp;

        private: UnsortedArray<Item, PQComp> T; 
		 static const int DEF_SIZE =270; 

};

Where Item is another class with the key and an object and min_element() gets that object.
Which uses an unsorted array to be implemented

template<typename ElemType, typename Comp>
class UnsortedArray {
public:

	UnsortedArray( int size = ARRAY_SIZE) { filled = 0; get_new_array(size); }

	void insert(const ElemType e);
	ElemType& min();

private:

	int filled;  //keeps track of how many elements in the array
	Comp comp; 
	int length;
	ElemType *array;

	void get_new_array(int new_size)
	{
		array = new ElemType[new_size];
		length = new_size;
	}

	static const int ARRAY_SIZE = 270; 

};

These are the functions used from UnsortedArray

template<typename ElemType, typename Comp>
void UnsortedArray<ElemType, Comp>::insert(const ElemType e) //Insert into the array
{
	array[filled] = e;

	filled++;

}

template<typename ElemType, typename Comp> // Find the minimum element
ElemType& UnsortedArray<ElemType, Comp>::min()
{
	if( is_empty() ) throw 1;

	ElemType temp= array[0];
	
	for(int i =0; i < filled-1; i++)
	{
		if(temp.get_key() > array[i+1].get_key())
		{
			temp = array[i+1];
		}
	}
	
	return temp;
}

[Oswld]

I could really use some pointers on this one if anyone can help please.

[ne555]

After filling some holes to make your code compile, I did not observe the crash.
However, ElemType& UnsortedArray<ElemType, Comp>::min() returns a reference to a temporary.

int main()
{
	PriorityQueue<Vertex*> pq;

	int x =32;
	Vertex* cloud= new Vertex(x);
	pq.insertItem(x,cloud);

	Vertex* c = pq.min_element(); 
	cout << c->getID();
}

`c' should be equal to `cloud', do a step-by-step run and find the error.

[Oswld]

That is curious, When i ran it several times before it gave the error, but now its not... I'm just confused as to what happened because i did not change anything mayor at all;
Anyways I'm now having another error with this function:

int find(ElemType& e)
	{
		return T.find_p(Item(0,e));
	}

template<typename ElemType, typename Comp>
int UnsortedArray<ElemType,Comp>::find_p(ElemType& e)
{
	if( is_empty() ) throw 1;

	ElemType temp= array[0];

	for(int i =0; i < filled-1; i++)
	{
		if(temp.get_elem() == array[i+1].get_elem())
		{
			return i+1;
		}
	}
	return 0;
}

It's telling me that no matching function to call to PriorityQueue<ElemType>::find(Vertex*x)

candidates are: int PriorityQueue<ElemType>::find(ElemType&) with ElemType = Vertex*

Im sorry to be bothering you much, if you could help me with this I'd really appreciate it

[Oswld]

The function searches for the element in the PQ and returns the location where it is stored. I did overloaded the == function for vertex.

bool operator== (Vertex& v, Vertex& nv)
{
	return ( v.getID() == nv.getID() && 
        v.getOutEdges() == nv.getInEdges() 
        && v.getInEdges() == nv.getOutEdges());
}

This is how i coded it.

[ne555]

I suppose that the problem is with const correctness.
You can't have a reference to a temporary, as you intend with T.find_p(Item(0,e));
Pass it by value, or by const-reference

[Oswld]

I get you, because the temp will not be there anymore after you leave the function so you cant really return by reference, right?

Well anyways, Thanks a lot for putting with me, i finally got my program to run, not getting the right output but at least im getting one this time!