What should function list<Edge> return?
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 we want to set V2's current distant to D and set V2's predecessor to V1.
I've declared and initialized V1 to the shortest distance (which is simply the initial point), and marked it as done.
Question: How do I declare a V2 and set it's distance?
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;
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[f开发者_运维百科romVertex] = UNDEFINED_PREDECESSOR;
done[fromVertex] = true;
for(int i =0; i < numVertices; i++){
if(!done[i] && distance[i] != INFINITY){
int V1 = getVertexWithSmallestDistanceThatsNotDone(distance, done);//choose smallest distance
done[V1] = true;//set vertice to to V1.
double D = distance[toVertex] + distance[predecessor[toVertex]];
if(D < distance[toVertex]){
D = distance[toVertex];
predecessor[toVertex] = fromVertex;
}
}
return listOfEdges;
}
}
You are returning a pointer to a std::list. You would normally allocate memory to this result in the function
std::list<Edge> *result = new std::list<Edge>();
Then, you would return this pointer
return result
In your outer function that grabs this result, you would need to free the memory that was dynamically allocated:
std::list<Edge>* edges = graph.shortestPath(1,5);
//work with edges
delete edges;
edges = NULL;//good practice to mark it as "not poiting to anything valid"
精彩评论