Bonjour.

Je viens solliciter votre aide pour coder en Java l'algorithme de Dijkstra, mais pas celui qu'on trouve partout sur Google avec les distances en fait. Moi j'ai un graphe, où les noeuds représentent les pages d'un livre. Et sur chaque noeud j'attribue un poids : 0 pour la 1ère page (la page mère), 1 pour les pages filles, 2 ... etc... jusqu'à la dernière page : la page 350. Et je dois sortir le chemin le plus court pour arriver à la page 350.

Avec mes collègues nous avons déjà la liste des pages ainsi que l'attribution correcte des poids par noeud, il nous reste plus qu'à faire la méthode pour sortir le chemin le plus court, mais on n'y arrive pas.

Merci d'avance pour votre aide.

C'est quoi la différence entre un poids et une distance, d'un point de vue algorithmique ?! Qu'est-ce qui change entre appliquer une "distance" représentant le poids d'une page n vers n+1 et une distance "normale" ?
C'est quoi en fait ton problème ?

En fait c'est au niveau du code que je sais pas trop comment faire. Une fois que j'ai le poids pour un chemin, comment lui faire comprendre que je veux maintenant calculer le poids pour le chemin à partir du noeud frère ? Je sais pas si tu vois ce que je veux dire...

Tu as bien compris le fonctionnement de l'algo, pour commencer ? C'est plutôt simple de le transcrire une fois que tu as saisi le principe. N'hésite pas à relire ton cours/la page wikipédia

Sinon, si tu galères, tu peux toujours utiliser une classe qui le fera à ta place : http://www.cs.nyu.edu/~vs667/development/~DijkstraAlgorithm/

J'ai pas de cours là-dessus, et la page Wikipedia... c'est justement elle que je n'arrive pas bien à comprendre, enfin... je comprends le principe mais pour mon post précédent je ne comprends pas. Merci pour le lien, mais c'est assez dur de comprendre un code étranger...

C'est quoi la différence fondamentale entre dijkstra et A*?

Rikkel, dijkstra calcule la distance (et le plus court chemin) entre un point et tous les autres points du graphe.

A* est utile pour calculer la distance (et le plus court chemin) entre un point et un point destination. A* est plus rapide que dijkstra si tu as une bonne estimation (borne inferieur) de la distance a la destination. Cela permet de ne pas considerer les chemin "qui s'eloigne" de la destination au debut de la recherche.

D'accord merci ! Je sais que jpourris un peu le topic avec mon HS mais... Si ça gène l'auteur vous pouvez supprimer mon post, mais est-ce que A* est efficace pour calculer la distance entre deux points qui changent de positions à chaque fois? (par exemple une course poursuite entre deux agents virtuels dans un labyrinthe)

rikkel, oui. La prochaine fois, fais un autre topic!

En fait, que ce soit avec Dijkstra ou un autre algorithme, mon but reste le même :

Sortir la liste de pages constituant le chemin le plus court pour arriver à la page 350.

Le graphe c'est celui-là : http://www.projectaon.org/en/svg/lw/01fftd.svgz
Donc la page 001 a un poids de 0. Les pages 141, 085 et 275 ont un poids de 1 etc...

Pour l'instant quand on exécute notre code, on a la liste des pages qui défilent, avec les poids correspondants. Et là il nous manque la méthode qui sort le chemin le plus court. Sur internet je n'ai trouvé que des trucs compliqués, où ils mettent TOUT leur code, avec leur graphe et tout... Personne ne donne juste la méthode vous voyez. C'est ça que j'aimerais avoir.

Help please.

La méthode est expliquée dans le premier paragraphe de la page wikipédia. L'alogrithme est donné dans le dernier paragraphe. Et il n'est pas compliqué du tout.

Quand je disais méthode c'était pour fonction (en Java quoi).