Discussion :

[CedricMocquillon]

Bonjour à tous

J'ai un problème sur l'agorithme de dijkstra, voici le code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
struct C_Graph
{
   vector<int>                   dist;
   vector<unsigned int>       pred;
   vector<vector<C_Arc*>> m_matOut; //les successeurs de chaque sommets (ptr d'arcs)
   void dijkstra (unsigned int start);
};
 
struct compare
{
   bool operator() (const pair<int, unsigned int>& p1, const pair<int, unsigned int>& p2) const
   {
      if (p1.first == p2.first)
         return p1.second < p2.second;
      return (p1.first > p2.first) ;
   }
};
 
void C_Graph::dijkstra (unsigned int start)
{
   size_t i,j;
   double alt;
 
   pair<int, unsigned int> p;
   set<pair<int, unsigned int>, compare> l_set;  //longueur, sommet
   set<pair<int, unsigned int>, compare>::iterator it_p;
   vector<C_Arc*>::iterator it_pArc;
 
   dist[start] = 0;
   dist.assign(m_nbNoeuds, (std::numeric_limits<int>::max)());
 
   pred.resize(m_nbNoeuds);
   for (i=0; i<m_nbNoeuds; ++i)
   {
      l_set.insert(make_pair(dist[i], i));
      pred[i] = i;
   }
 
   for (i=0; i<s_vctNoeuds.size(); ++i)
   {
         it_p = l_set.end();
         --it_p;
         p = *(it_p);
         l_set.erase(it_p);
         for (it_pArc=m_matOut[p.second].begin(); it_pArc != m_matOut[p.second].end(); ++it_pArc)
         {
            j = (*it_pArc)->second;
            alt = double(dist[p.second] +(*it_pArc)->m_iDistance);
            if (alt < double(dist[j]))
            {
                  l_set.erase(l_set.find(make_pair(dist[j], j)));
                  l_set.insert(make_pair(alt, j));
                  dist[j] = alt;
                  pred[j] = (*it_pArc)->m_uiId;
            }
         }
   }
   l_set.clear();
}

Ce code fonctionne bien, mais j'ai des problèmes de performances, j'appelle cette fonction un grand nombre de fois, mon nombre de noeuds étant constant entre deux appels, j'ai resizé les vecteurs dist et pred (il n'y a donc pas de réallocation entre deux appels). Je pense que ce qui me fait le plus perdre de temps c'est la partie en lien avec le set (utilisé pour la version améliorée du dijkstra). Voilà, si quelqu'un a déjà essayé de programmer cet algo à l'aide de la STL, je suis prenneur de tout exemple et conseils pour l'améliorer

[PierroElMito]

Est-ce que les coûts des arcs changent entre chaque appels? Parce que si ils sont relativement constants et que ton nombre de noeud est assez faible, tu peux précalculer les chemins de chaque neoud vers tous les autres (algo de Floyd-Warshall). Ca permet ensuite de trouver le plus chemin sans aucun calcul.

[befalimpertinent]

Encore plus rapide que Dijkstra ou que Floyd-Warshall : l'algorithme A star

[PierroElMito]

ces 3 algos ne font pas la même chose donc ne sont pas comparable au niveau vitesse:
- A* : donne un plus court chemin entre deux noeud
- Dijskstra : tous les plus courts chemins vers ou depuis un noeud
- Floyd-Warshall : tous les plus courts chemins entre tous les noeuds du graphe

leur utilisation dépend du problème à traiter. si tu peux précalculer tous les chemins parce que le graphe est statique, utiliser Floyd-Warshall sera plus performant que d'appeler A* à chaque fois que tu cherches un chemin.

[CedricMocquillon]

En fait mon graphe correspond à un graphe routier et je recherche les plus court chemins en temps. L'algorithme A* ne me semble donc pas convenir (il est basé sur une heuristique de distance euclidienne, ce qui ne marche pas avec l'aspect temporel: on va plus vite sur autoroute). Pour ce qui est de précalculer les chemins, je ne peux pas les précalculer (environ 12000 noeuds soit une matrice 12000*12000) (mon graphe est de plus orienté, je ne peux donc pas stocker la matrice triangulaire)

[PierroElMito]

A mon avis, A* peut marcher dans ton cas si ton heuristique renvoie la distance entre les noeuds divisée par une vitesse maximale.

[CedricMocquillon]

Le problème c'est qu'ensuite, j'utilise le code "basique" du dijkstra pour le faire en temporisé. Les valuations des arcs dépendent du moment où on arrive sur l'arc. J'utilise en plus une version inversée du dijkstra temporisé: on connait l'heure d'arrivée au noeud et il faut trouver le plus court chemin temporisé (cela nous donne les heures de passage par chaque arc et l'heure de départ du noeud de départ). Je ne connais pas très bien l'algorithme de A* et je pense qu'il vaudrait mieux que j'améliore la version basique du dijkstra (pour en faire bénéficier mes autre versions).