Page 1 sur 1
modélisation d'un graphe
Publié : mer. 27/juin/2007 16:51
par minirop
bonjour,
pour m'essayer à l'algo de dijkstra, jai besoin d'un graphe, mais je ne sais pas comment le modéliser en PB.
voilà un exemple de ce que je peux/veux avoir :
http://www.siteduzero.com/uploads/fr/fi ... /73425.jpg
c'est surtout pour les liens que je pêche (les villes étant des points et les distances peuvent être calculer avec la racine carré de la différence des distances).
merci.
Publié : mer. 27/juin/2007 17:15
par lionel_om
J'avais fais un programme en C pour mon école.
Les sources et le rapport sont dispo
ici, choisir NF16, TP6.
Ce prog utilise les listes simplement chaînées et Dijsktra pour choisir le plus court chemin. je pense quil est facilement adaptable...
Sinon il doit y avoir pleins de sources sur Internet.
Lio
Publié : mer. 27/juin/2007 17:25
par minirop
assez zarb le code, pas tout compris. Mais en fait je cherche juste la représentation du graphe en mémoire, pas l'algo.
le tien on dirait un tableau bi directionnel où chaque ligne n'a pas la même taille.
Publié : mer. 27/juin/2007 17:28
par lionel_om
minirop a écrit :assez zarb le code, pas tout compris. Mais en fait je cherche juste la représentation du graphe en mémoire, pas l'algo.
le tien on dirait un tableau bi directionnel où chaque ligne n'a pas la même taille.
Exact. C'est comme ça qu'ils voulaient qu'on le modélise : liste de listes.
Un truc comme ça tu veux :
Code : Tout sélectionner
Structure GPoint
nom.s
; tout ce que tu veux d'autre...
EndStructure
Structure GArc
*point1.GPoint
*point2.GPoint
distance.f
EndStructure
NewList Graphe.GArc()
Lio
Publié : mer. 27/juin/2007 17:44
par minirop
j'ai réussi à afficher mon graphe.
image
me reste à implémenté l'algo
