Implémentation de l'algo de Dijkstra en C

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

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

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...

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

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

salut,

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

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

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

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

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

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

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

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

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

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.....

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++

je ve lalg de djikstra. svp tré urgen?

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

je veut l'algorithme de plus court chemin

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