Discussion :

[WoumWoum]

Bonsoir,

Pour vous aider à situer la chose, en résumant, j'ai implanter l'algorithme de dijkstra sur des graphes en C++ avec la file de priorité tableau décroissant.
Je le fais afin de faire des test pratique sur les tableaux décroissants puis ensuite les tas binomiaux.

Après avoir créé mes différentes classes, je me rends compte (après plusieurs test) que ce qui ralenti mon programme est la récupération du poids de 2 arrêtes, 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
class Voisin
{
private:
	int _sommet;
	double _poids;
[...]
};
 
class TabVoisin
{
private:
	list<Voisin> _liste;
	Point _coordonnee;
[...]
};
 
class Graphe
{
private:
	int _nbsommet;
	vector<TabVoisin> _tableau;
public:
[...]
double Poids(int u, int v);
[...]
};
 
double Graphe::Poids(int u, int v)
//On est sûr que u et v sont relié
{
	vector<TabVoisin> TV=this->get_TabVoisin();
	TV[u].get_liste();
	list<Voisin> L=TV[u].get_liste();//Renvoie _liste
	while(!L.empty())
	{
		if(L.front().get_sommet()==v)
			return L.front().get_poids();
		L.pop_front();
	}
}

Pour être sûr que c’est cette fonction qui me fait lagger, mon programme se lance en 2 secondes quand je remplace ce code par :

Code :

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

1
2
3
4
5
double Graphe::Poids(int u, int v)
//On est sûr que u et v sont relié
{
return(1);
}

Et lorsque je le laisse, il mets plusieurs minutes à se lancer. Le graphe possède 200 sommets avec environ une 40aine d'arrêtes par sommet.
Une explication :/ ?

[Invité]

hello,

à chaque fois tu copies tes tableaux

Code :

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

1
2
vector<TabVoisin> TV=this->get_TabVoisin();
list<Voisin> L=TV[u].get_liste();//Renvoie _liste

Donc forcément, c'est lent si t'as mass de noeuds.

pourquoi utiliser get_TabVoisin et pas directement _tableau.
const list<Voisin> &l = _tableau[u].get_liste();

(avec const &std::list<Voisin> TabVoisin::get_liste()const (note surtout la référence))
Et après au lieu de popper ta liste (pourquoi une liste et pas un set?), tu itères simplement: (avec std::find_if ou à la main comme ci-dessous)

Code :

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

1
2
3
4
5
6
 
	for(std::list<Voisin>::const_iterator it=l.begin(); it!=l.end(); ++it)
	{
		if(it->get_sommet()==v)
			return it->get_poids();
	}

[WoumWoum]

Bonjour,

Comme quoi c'est en pratiquant que l'on apprends :/. Et je vois aussi pourquoi il aurait été plus malin d'utiliser un set plutôt qu'une liste.

En tout cas merci, tu avais raison ! Grace à toi je vais passer un meilleur week-end (oui ça me faisait déprimer :p).