0

I'm implementing dijkstra's algorithm, and I'm implementing it using a priority queue so that the shortest distance is on top for fast access. The priority queue uses a vector for its operations.

Each node has the following properties:

int id
int dist
Node *path

Here is the issue: when I attempt to rearrange the priority queue (i.e. swap two elements during a percolate function to keep the lowest distance on the top), they overwrite eachother. So, let's take this example:

Vector:
[1] = node1
[2] = node2
[3] = node3

Node 3's path points to node 1.

Now when I attempt to swap indexes 3 and 1 using a temp variable and assignment statements, node 1 becomes node 3, and node 3's path member points to itself infinitely, destroying what I have of my path so far.

Summary: I need to be able to swap elements without them overwriting eachother.

This problem has been killing me. I've spent 6+ hours on it. Thank you for your help.

2
Contributors
1
Reply
2
Views
8 Years
Discussion Span
Last Post by siddhant3s
0

A general swap algorithm is :

//say you want to swap var1 and var2
temp= var1;
var1=var2;
var2=temp;

In c++ you can use the ready made function std::swap() defined in <algorithm> header file which can do this job for you.

//    swaps the content of m-th element of a vector vec, with the
//    n-th element of the same vector
std::swap(vec[m],vec[n]);
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.