Bonjour à tous,

J'essaie d'implémenter l'algorithme de Bellman-Ford qui permet de calculer les plus courts chemins à partir de sommets sources dans un graphe orienté pondéré. Je crois que mon implémentation donne le bon résultat (ce que je ne peux vérifier) mais mon programme tourne beaucoup trop lentement. J'aimerais donc l'accélerer de manière significative. 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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <array>
#include <map>
#include <fstream>
#include <climits>
#include <set>
 
struct Edge
{
	unsigned int tail;
	unsigned int head;
	int length;
} ;
 
struct Key
{
	long unsigned int q;
	long unsigned int t;
};
 
struct KeyCompare {
	bool operator()(const Key& a, const Key& b){
		return (a.q < b.q) or (a.q == b.q and a.t < b.t);
	}
};
 
typedef std::map<Key, int, KeyCompare> Graph;
 
Graph get_graph();
int** initialize(unsigned int source);
void compute(int** & tab);
Edge compute_min_edge(unsigned int source, Graph g);
 
Edge compute_min_edge(unsigned int head_, Graph g){
	Edge e({INT_MAX, head_, INT_MAX});
	for(unsigned int x(0); x < 1000; ++x){
		if(g.find({x, head_}) != g.end()){
			if(g.find({x, head_})->second < e.length){
				e.length = g.find({x, head_})->second;
				e.tail = x;
			}
		}
	}
 
	return e;
}
 
 
Graph get_graph(){
	Graph graph;
	std::string ligne("");
	std::ifstream fichier("g1.txt", std::ios::in);
 
	if(fichier){
		getline(fichier, ligne);
		while(getline(fichier, ligne)){
			Key k = {stoul(ligne.substr(0, ligne.find(' ', 0)))-1, stoul(ligne.substr(ligne.find(' ', 0), ligne.find(' ', ligne.find(' ', 0) + 1)))-1};
			graph[k] = stoi(ligne.substr(ligne.find(' ', ligne.find(' ', 0) + 1)));
		}
	}
 
	return graph;
}
 
int** initialize(unsigned int source){
	unsigned int dimX = 1000, dimY = 47978;
	int** tableau;
 
	tableau = new int*[dimX];
	for(size_t x(0); x < dimX; ++x){
		tableau[x] = new int[dimY];
		for(size_t y(0); y < dimY; ++y){
			tableau[x][y] = INT_MAX;
			if(y == 0 and x == source)
				tableau[x][y] = 0;
		}
	}
 
	return tableau;
}
 
void compute(int** & tab, Graph g){
	for(size_t i(1); i < 47978; ++i){
		for(size_t j(0); j < 1000; ++j){
			Edge e(compute_min_edge(j, g));
			tab[i][j] = std::min(tab[i-1][j], tab[i-1][e.tail] + e.length);
			std::cout << " i " << i << std::endl;
		}
	}
}
 
 
int main(int argc, char* argv[]){
 
	Graph graph(get_graph());
 
	int** tab(initialize(0));
 
	compute(tab, graph);
 
	return 0;
}
Comme vous pouvez le voir 3 fonctions sont appelées dans le main, les deux premières cumulées tournent en moins de 1 sec donc le problème vient de la fonction "compute". Or dans cette fonction il y a deux choses principales, une double boucle que je ne peux pas éviter à ma connaissance, des "look-up" répétés dans ma map qui contient mes arêtes. J'imagine que c'est donc ici que je perds du temps. Si quelqu'un a la moindre idée sur la manière d'accélerer mon programme que ce soit avec mes structures ou avec d'autres je vous serais reconnaissant d'en faire part , merci à tous.