|
|
|
|
Bonjour,
je cherche à implémenter l'algorithme de Dijkstra en C afin de réaliser un programme de calcul du court chemin.
La vitesse d'exécution est un critère important donc je dois choisir une structure de donnée adaptée.
J'ai entendu que le tas de Fibonacci est la structure optimale pour cet algorithme. Mais je ne sais pas du tout comment réaliser cette structure !
Quelqu'un aurait il une suggestion, ça m'aiderait beaucoup ! Merci d'avance !
Salut,
|
Tiens c'est marrant j'en ai programmé un aujourd'hui, mais en c++. Tu peux te baser comme moi sur cette page :
|
Je t'invite à relire les deux liens que j'ai donné précédemment :
|
Si c'est une matrice c'est tout s'implement que tu appliques un Dijkstra en prenant pour source plusieurs (ou la totalité des) sommets du graphe.
typedef unsigned int vertex_t;
typedef unsigned int weight_t;
void dijkstra(
const graph_t & g, // le graphe
const vertex_t & src, // le sommet source
std::vector<vertex_t> & succs,
std::vector<weight_t> & poids
){
// mon algo remplit succs et poids
}
...qui sera appelée par une fonction qui calculera toute la matrice void dijkstra_matrix(
const graph_t & g, // le graphe
std::vector<std::vector<vertex_t> > & succs_mat,
std::vector<std::vector<weight_t> > & poids_mat
){
vertex_t vit=0;
vertex_t vend=g.card_v(); //retourne le nombre de sommets
for(vit = 0 ; vit != vend ; ++vit){
//calculer le dijkstra pour la source courante
std::vector<vertex_t> succs = std::vector<vertex_t>(g.card_v());
std::vector<weight_t> poids = std::vector<weight_t>(g.card_v());
dijkstra(g,vit,succs,poids);
succs_mat.push_back(succs);
poids_mat.push_back(poids);
}
}
Il faut par ailleurs : - soit implémenter une classe de graphe - soit repartir d'une classe de graphe d'une lib existante, genre la lib boost - soit se baser sur une matrice d'adjacence décrivant le graphe, dans laquelle il faudra caractériser un poids infini pour les sommets non adjacents. Bonne chance |
Répondre à mamiemando
|
| Répondre à doudou |
Algo tri c Algo tri c# C jeu algo débutant C cleaner C'est pas bien Dev c Free c Implementation reseau neurone c Implementation tri rapid c Implémentation une application en c# Langage c Microsoft silverlight c'est quoi Microsoft visual c runtime library Modulo c Msxml 4.0 sp2 c'est quoi Partie entiere c Runtime error visual c ç majuscule
