Posez votre question Format imprimable Liste des forums Aidez-les Statistiques Rechercher Charte Forum Programmation

Statut : Non résolu

Implémentation de l'algo de Dijkstra en C

Thierry, le mardi 20 décembre 2005 à 20:51:24

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 !

Répondre à Thierry Signaler ce message aux modérateurs Aller au dernier message

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

bacchuss, le mardi 20 décembre 2005 à 21:49:34

salut,

http://www.commentcamarche.net/forum/affich-1879211-demande-d-un-algorithme-de-plus-court-chemin __________________________________________
01001001110101001010100101 et plus si affinités

Répondre à bacchuss

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

Thierry, le mardi 20 décembre 2005 à 22:47:37

Salut, je n'ai malheureusement pas trouvé ce que je cherchais sur ce post.

Mais merci quand même, c'est le geste qui compte ...

a+

Répondre à Thierry

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

mamiemando, le mercredi 21 décembre 2005 à 00:46:36

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

Répondre à mamiemando

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

noucha000, le dimanche 6 mai 2007 à 23:40:29

salut mamiemando!!!
je suis nouvelle sur le site ! je cherche le code de l'algorithme du plus court chemin de dijkstra. si vous pouvez m'aidez cela me fera très plaisir. mon adresse: mariamoutman@yahoo.fr
merci d'avance!!!

Répondre à noucha000

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

spamware, le vendredi 14 avril 2006 à 12:01:23

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

Répondre à spamware

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

mamiemando, le vendredi 14 avril 2006 à 13:50:58

Je t'invite à relire les deux liens que j'ai donné précédemment :
http://www.apprendre-en-ligne.net/graphes/dijkstra/algorithme.html
http://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

Répondre à mamiemando

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

spamware, le vendredi 14 avril 2006 à 17:29:19

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

Répondre à spamware

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

mamiemando, le vendredi 14 avril 2006 à 19:11:37

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

Répondre à mamiemando

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

spamware, le vendredi 14 avril 2006 à 19:50:21

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

Répondre à spamware

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

mamiemando, le vendredi 14 avril 2006 à 20:41:26

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

Répondre à mamiemando

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

spamware, le vendredi 14 avril 2006 à 21:45:38

je trouve que pour implementer l'algo de dijkstra en c est un peu compliquer et c'est pas aussi simple que tu le dis , j'ai bien compris le principe mais je seche dans les iterations et merci quand meme

Répondre à spamware

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

mamiemando, le vendredi 14 avril 2006 à 22:09:59

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

Répondre à mamiemando

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

spamware, le dimanche 16 avril 2006 à 16:57:52

salut, je dois utiliser 2 matrices l'une contient les successeures et l'autre contient le poid de chaque arcs , c 1 tp que je dois rendre prochainement alors si tu a l'algo de dijkstra en c tu peux me le donner pour voir l'idée merci

Répondre à spamware

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

mamiemando, le mardi 18 avril 2006 à 18:55:47

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

Répondre à mamiemando

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

spamware, le mardi 18 avril 2006 à 19:54:11

salut , je te remercie pour ton aide mais j'ai pas eu de probleme pour construire les deux matrices , mon prg doit afficher :
a chaque etape l'ensemble s et s'
afficher en dernier etape la liste des plus court chemins entre tt couple
de sommets ainsi que leurs valeurs.
et merci encore

Répondre à spamware

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

douja, le vendredi 11 janvier 2008 à 15:20:13

slt.pouvez vous médé pour lalg de djikstra le plus to ossibl stp. é merci en avance

Répondre à douja

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

mamiemando, le jeudi 20 avril 2006 à 12:29:41

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

Répondre à mamiemando

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

spamware, le jeudi 20 avril 2006 à 16:06:10

c bon j'ai reussi a l'implementer tt seul

Répondre à spamware

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

noucha000, le dimanche 6 mai 2007 à 23:46:58

salut sapamware
c'est urgent!!!
je suis nouvelle sur le site.
je cherche le code du plus court chemin de dijkstra en c++ ou bien en c. si tu peux m'aider? mon adresse mariamoutman@yahoo.fr
merci d'avance!!!

Répondre à noucha000

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

mamiemando, le lundi 7 mai 2007 à 13:20:34

En C++ avec la lib boost :
http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html

Un exemple
http://www.boost.org/libs/graph/example/dijkstra-example.cpp

Pour compiler, après avoir installé boost :

g++ -W -Wall -I/usr/include/boost dijkstra-example.cpp

Bonne chance

Répondre à mamiemando

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

Mouna, le lundi 19 février 2007 à 14:23:49

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

Répondre à Mouna

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

doudou, le dimanche 30 décembre 2007 à 13:19:28

je ve lalg de djikstra. svp tré urgen?

Répondre à doudou

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

noucha000, le mardi 1 janvier 2008 à 22:29:25

envoie moi ton mail je vais t'envoyer l'algorithme implémenté en c.

Répondre à noucha000

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

douja, le vendredi 11 janvier 2008 à 15:14:17

salu,comen sa va stp pe tu menvoyé lalg de djikstra le plu to poss .merci davance

Répondre à douja

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

allal, le dimanche 15 juin 2008 à 10:45:18

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

Répondre à allal

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

Legacy, le mercredi 25 juin 2008 à 17:46:58

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

Répondre à Legacy

Ce message vous semble utile, votez !
Signaler ce message aux modérateurs

TURBOXPLAY, le dimanche 28 septembre 2008 à 19:49:02

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

Répondre à TURBOXPLAY

Posez votre question Répondre