Plus court chemin Dijkstra STL
Bonjour à tous
J'ai un problème sur l'agorithme de dijkstra, voici le code:
Code:
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
