Comment affiner l'algorithme de Dijkstra, ne pas trouver le chemin optimal

Question

Voici mon implémentation de l'algorithme de Dijkstra bien connu:

std::vector<unsigned> RouteFinder::findPathBetweenIntersections(unsigned intersect_id_start, unsigned intersect_id_end) { 

    //Get number of intersections and reference graph from streetGraph class 
    StreetGraph* streetGraph = StreetGraph::getGraphPointer(); 
    unsigned intersectionCount = streetGraph->getIntersectioncount(); 
    std::vector<attachedSegments> referenceGraph = streetGraph->getStreetGraph(); 

    /*Initialize: 
    * min_distance: Min Distance to get to index node 
    * active_vertices: The nodes to check next 
    * cameAlong: Street Segments used to get to the node 
    * cameFrom: Intersections taken to get to a node 
    */ 
    vector<double> min_distance(intersectionCount, DBL_MAX); 
    min_distance[ intersect_id_start ] = 0.0; 

    set< pair<double,unsigned> > active_vertices; 
    active_vertices.insert({0.0,intersect_id_start}); 

    vector<unsigned> cameAlong(intersectionCount,UINT_MAX); 

    vector<unsigned> cameFrom(intersectionCount,0); 

    //For each node in active_vertices 
    while (!active_vertices.empty()) { 
     unsigned currentNode = active_vertices.begin()->second; 
     if (currentNode == intersect_id_end) return buildPath(cameFrom, cameAlong, currentNode, intersect_id_start); 
     active_vertices.erase(active_vertices.begin()); 
     for (auto edge : referenceGraph[currentNode].streetSegments) 
      if (min_distance[get<2>(edge)] > min_distance[currentNode] + get<0>(edge)) { 

       //If the new distance is better than the one that is there 
       //Remove the previous data 
       active_vertices.erase({ min_distance[get<2>(edge)], get<2>(edge) }); 
       //Calculate the better distance and replace it 
       min_distance[get<2>(edge)] = min_distance[currentNode] + get<0>(edge); 

       //Add 15 seconds if the street has changed 
       if ((cameAlong[currentNode] != UINT_MAX 
         && getStreetSegmentInfo(cameAlong[currentNode]).streetID != getStreetSegmentInfo(get<1>(edge)).streetID) 
         ) { 
        min_distance[get<2>(edge)] = min_distance[get<2>(edge)] + .25; 
       } 

       active_vertices.insert({ min_distance[get<2>(edge)], get<2>(edge) }); 

       //Record where you came from 
       cameAlong[get<2>(edge)] = get<1>(edge); 
       cameFrom[get<2>(edge)] = currentNode; 
      } 
    } 

    //Return nothing if nothing found 
    vector<unsigned> nothing; 
    return nothing; 
} 

Mon graphique est un vecteur de structures appelées « intersectionNode ». Chaque "intersectionNode" a un vecteur (parmi d'autres informations utiles) de tuple<double weight,int streetSegment,int nextIntersection>.

J'ai adapté mon implémentation à partir d'exemples que j'ai trouvés en ligne et d'amis, c'est assez rapide. Mais il ne semble pas retourner le chemin le plus rapide. Est-ce que quelque chose vous saute aux yeux, des conseils pour le débogage?

En outre, j'ai incorporé une pénalité d'exécution de .25 minutes (15 secondes).

Merci pour l'aide!

Answer 1

J'ai trouvé la réponse! Lorsque vous comparez de nouveaux chemins par rapport aux anciens chemins. Je n'ai pas pris en compte les coûts de tournage. Merci les gars ...