开发者

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"
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜