Implémentation de l'algo de Dijkstra en C Fermé

Question

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 !

mamiemando · Accepted Answer

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.

L'algorithme de Dijkstra retourne un vecteur de poids et un de successeurs. Il suffit donc de mettre ces vecteurs les uns en dessous des autres pour obtenir les deux matrices dont tu parles.

Idéalement tu peux coder un algorithme de dijkstra qui prend en paramètre :
- le graphe (ou la matrice décrivant le graphe)
- le sommet source
... et qui retourne :
- le vecteur de poids
- le vecteur de successeurs

On va supposer que les sommets sont identifiés par un entier pour simplifier, et que les arcs sont pondérés par un entier positif

Exemple :

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

bacchuss · Answer

salut,http://www.commentcamarche.net/forum/affich-1879211-demande-d-un-algorithme-de-plus-court-chemin

mamiemando · Answer

Tiens c'est marrant j'en ai programmé un aujourd'hui, mais en c++. Tu peux te baser comme moi sur cette page :
http://www.apprendre-en-ligne.net/graphes/dijkstra/algorithme.html

Je viens de tomber sur une implémentation c++ ici mais ça te parle peut être moins :
http://www.nimbustier.net/publications/djikstra/implementation.html

Quoiqu'il en soit il faut que tu attrapes le reflexe GOOGLE !!!!! :-)

Bonne chance

spamware · Answer

salut , je chercher l'algo de dijkstra en c ,  j'ai trouver sur google plusieurs algorithmes mais j'ai rien compris a la stucture alors si vous pouvez m'aider                      merci

mamiemando · Answer

Je t'invite à relire les deux liens que j'ai donné précédemment :
http://www.apprendre-en-ligne.net/graphes/dijkstra/algorithme.html
https://www.nimbustier.net/publications/djikstra/implementation.html

Anvant de s'attaquer à la compréhension du programme en C, il faut déjà avoir bien compris le principe de l'algorithme lui même :

1) Initialisation
- on choisit une source
- on initialise un vecteur de prédecesseurs et de poids

2) Itération
- on cherche l'arc de poids minimal se raccrochant aux sommets traités
- on met à jour le vecteur de prédécesseurs et de poids

A l'issue de l'algorithme le vecteur de poids te donne le poids du plus court chemin pour chaque sommet du graphe, et le vecteur de prédecesseurs le sommet duquel il faut venir pour l'atteindre de manière optimale.

On est dès lors en mesure de reconstituer les plus court chemin partant de la source pour chaque sommet du graphe à partir du vecteur de prédecesseurs.

Bonne chance

spamware · Answer

merci,  mais j'ai deja  visiter ces sites et ca ma pas trop aider

mamiemando · Answer

As-tu compris l'algorithme en lui même au delà de l'implémentation ?

spamware · Answer

oui j'ai tres bien compris l'algo de dikstra , j'ai meme resolu  des exercises concernant l'algo mais j'ai pas reussi a l'implementer en c j'ai essayé plusieurs methodes sans aboutir a un resultat

mamiemando · Answer

Ben là c'est juste du C... Il faudrait que tu nous donnes ton algorithme pour qu'on voit ce qui déconne. Mais normalement si tu transpose les algos donnés dans les liens ci-dessus il n'y a pas de soucis.

Bonne chance

mamiemando · Answer

Donne moi ton code et on va essayer de voir (par contre je ne suis pas là ce week-end)...

mamiemando · Answer

Donne moi ton code actuel et on va regarder ça... Mais a priori c'est vraiment très simple, je suis un peu surprise que ça te bloque...

Mouna · Answer

Salut,
je cherche à implémenter l'algorithme de Dijkstra en matlab afin de réaliser un programme de calcul du court chemin

doudou · Answer

je ve lalg de djikstra. svp tré urgen?

allal · Answer

merci mais je veu les procedures suivantes de l'Initialisation et l'ajout et suppression et l'affichage d'un graphe

Legacy · Answer

Bjr,
je voudrais avoir le code C++ des algo Kruskal(à l'aide des ensembles disjoints et files de priorités dynamique) et de Prim

TURBOXPLAY · Answer

slt, j'ai b1 lus les différentes reponses, mais moi je voulais plus cette implémentation en C++, si quelqu'un peut m'aider ça me fera très plaisir.....

informatique · Answer

si tu trovez le solution envoier a la mail mlahcine@yahoo.fr

salimasalima80 · Answer

je veut l'algorithme de plus court chemin

ARAKAZA ALEXIS · Answer

je souhaiter une fonction enC/C++ qui  facilte le plu bien possible  de voyage d'une ville A à une villeB tout en minimisant le cout de voyage ce derneir est calculé selon la distance reliant les deux ville et sachant que je dispose de beaucoup de ville dans les quelle on peut passer appliquer l'algo du plu cours chemin merci

Vicking54 · Answer

moi j'ai eu un projet cette année qui était le calcul du plus court chemin dans des graphes pour plusieurs milliers de noeud, avec tableau trié dans l'ordre décroissant et tas binomaux. mais on trouve les algo qu'il faut sur google et a toi de l'adapter à tes besoins. Personnellement j'ai tous programmé en C++

Implémentation de l'algo de Dijkstra en C

20 réponses

Discussions similaires