Hello,
I'm trying to complete dijkstra's algorithm but I'm having a really hard time figuring it out.
I've made a table with three array's that will keep track of the distance, predecessor, and whether the vertex is done or not.
My initial vertex's distance is set to 0, predecessor set to UNDEFINED, and TRUE for whether it's been visited or not.
Then I've marked my initial point as V1 and adjusted the distance, predecessor, and done of my initial point being the lowest distance that's not infinity.
Now what I want to do is, for each edge leading from V1 to V2, I want to set the distance(D) of V2 from V1. And if D is less than the current distant to V2 then I want to set V2's current distant to D and set V2's predecessor to V1.
How would I first initialize V2?
Thanks. =]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
|
std::list<Edge>* Graph::shortestPath(int fromVertex, int toVertex){
//initialize distance array set to INFINITY
//initialize predecceor set to -1
//initialize bool done array to false
std::list<Edge> *listOfEdges = new std::list<Edge>();
std::list<Edge>::iterator it;
int v1=0;
int v2=0;
Edge *edge;
double *distance = new double [numVertices];
int *predecessor = new int [numVertices];
bool *done = new bool [numVertices];
for(int i =0; i < numVertices; i++){
distance[i] = INFINITY;
predecessor[i] = -1;
done[i] = false;
}
distance[fromVertex] = 0;
predecessor[fromVertex] = UNDEFINED_PREDECESSOR;
done[fromVertex] = true;
for(int i =0; i < numVertices; i++){
if(!done[i] && distance[i] != INFINITY) //which vertex is the only one thats not INFINITY? Our initial one!
v1 = getVertexWithSmallestDistanceThatsNotDone(distance, done);//choose smallest distance
else
done[v1] = true;//set vertice to to V1.
}
for(int i =0; i < numVertices; i++){
}
return listOfEdges;
}
|