Finding shortest path!

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.
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152`` ``````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 pq; //Priority Queue while(igetID() == 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?
Last edited on
> 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
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
 ``1234567891011121314`` ``````int main() { PriorityQueue 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.
Good, that's quite small to look at.
Yes, post those functions
Ok the basic stuff that im using for what i posted is this
 ``1234567891011121314151617181920`` ``````template 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 Item; typedef PQComp PQComp; private: UnsortedArray 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
 ``1234567891011121314151617181920212223242526`` `````` template 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
 ``12345678`` ``````template void UnsortedArray::insert(const ElemType e) //Insert into the array { array[filled] = e; filled++; }``````

 ``123456789101112131415161718`` ``````template // Find the minimum element ElemType& UnsortedArray::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; } ``````

Last edited on
I could really use some pointers on this one if anyone can help please.
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.

 ``1234567891011`` ``````int main() { PriorityQueue 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.
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:
 ``12345`` ``````int find(ElemType& e) { return T.find_p(Item(0,e)); } ``````

 ``123456789101112131415161718`` `````` template int UnsortedArray::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
The function searches for the element in the PQ and returns the location where it is stored. I did overloaded the == function for vertex.
 ``1234567`` `````` 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.
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
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!
Last edited on
Topic archived. No new replies allowed.