GRAPHE ORIENTÉ ET DIJKSTRA

Commentaire de Bel0 le 26/04/2005 13:45:44

C'est normal. Il faut plutot voir cette source comme une "mini-librairie" pour les graphes et Dijkstra.

Commentaire de tiburcedavy le 23/05/2005 21:04:36

je suis sur un projet réseau et j'aimerais que tu m'envoies tout le contnue du projet réseau à:
tiburcedavy@yahoo.fr
avec mes remerciements

Commentaire de POLYPHAGE le 07/11/2005 09:41:47

Bonjour,
dans le cadre d'un projet d'informatique (de recherche operationnelle), nous avons besoin de gerer un arbre de loterie et de trouver des chemins les plus courts/longs.
Le code joint a cette page me permet elle de faire ca? si oui comment gerer ca?
s'il est possible de repondre sur polyphage@hotmail.com
merci.

Commentaire de plsvse le 14/11/2005 18:54:25

je souhaiterai savoir si il peut s'adapter sur un graphe ou il y aurait des obstacles sur le parcours et ainsi et éviter qu'il se cogne à chacun des obstacles pour s'en sortir
Merci

Commentaire de mechesBlondes le 22/11/2005 23:44:37

Arrete de robber plsvse. C'est pas comme ça que tu auras ton diplome d'ingénieur.
Implémente le, tu apprendra plus de chose. Et puis Bellman-Ford est plus optimisé.

Commentaire de julie_deluy le 23/11/2005 13:29:37

Je suis nouvelle sur ce site pour mettre mon aide au service des autres. J'ai codé en java de nombreux algorithmes du plus court chemin dont dijkstra et AStar. En ce qui concerne les obstacles, AStar est plus approprié. Il suffit d'optimiser AStar pour obtenir des temps d'exécutions relativement corrects.

Vous pouvez me contacter par mail sur deluy_julie@hotmail.fr (J'ai aussi MSN si vous avez)

Je trouve completement idiot le message de MechesBlondes, on est ici pour s'aider les uns les autres.

Commentaire de toufiq22 le 19/02/2006 16:17:53

Moi aussi je serais intéressé par le code pourrais tu me l'envoyer stp??
mctoufiq@gmail.com

Commentaire de abdo_kabrane le 26/02/2006 00:06:13

moi je sui trs interessé par cet algo de dijkstra car g un projet de fin d'etude ki a comm but de trouver le chemin le plus court
c klk 1 pe m'aider sa sera un grand plaisir de leur part
bonn courage a tt le monde

Commentaire de Bel0 le 09/04/2006 01:05:11

Avant, désolé de ne pas répondre plus rapidement mais ca fait un bout de temps que j'ai posté ce code et je ne vérifie pas tout le temps s'il y a des nouveaux commentaires.

julie_deluy: A* est en effet très correct pour trouver le chemin le plus court vers une destination. Si on veut trouver la distance la plus courte vers n points, il faut faire tourner n fois A*. L'avantage de Dijkstra est que toutes les distances sont calculées en une fois (c'est ce que je voulais dans le projet incluant cet utilitaire).

dj leemon: Ah, j'avoue que les noms ne sont pas forcement des plus  claires :p. C'est en fait lier au fonctionnement de la file. L'implémentation est basé sur un tas (heap).

Pour avoir une idée (très grossière) de son fonctionnement, voici quelques explications:

On peut voir l'implémentation de la file par un tas comme un arbre dans lequel on stocke des nombres, le nombre le plus petit se situant au sommet. Cet arbre a une propriété spéciale (pour pouvoir en faire un tas): le nombre stocké dans chaque enfant est plus grand (ou égal) au nombre stocké dans le parent. Il y a deux opérations principales sur cet arbre: ajouter un nouveau nombre, retirer le nombre le plus petit.

Ajout d'un nombre:
on ajoute ce nombre en bas à droite de l'arbre et on le fait remonter (comme une bulle donc :)) jusqu'à ce que le nombre du parent soit plus petit que le nouveau nombre insérer.

Retrait du nombre le plus petit:
Le nombre le plus petit est toujours au sommet de l'arbre (par construction). On retire donc cet élément mais on ne peut pas laisser un "trou" au sommet de l'arbre. On prend donc l'élement en bas à droite dans l'arbre et on le place au sommet. A ce moment, on ne respecte plus la propriété de l'arbre et on doit donc descendre ce nombre jusqu'à les enfants de ce nombre soient plus grand que celui-ci.

Maintenant quel est le rapport entre l'arbre et le tableau ? L'arbre est en fait un arbre un peu particulier puisqu'on le remplir niveau par niveau et on ne commence pas un nouveau niveau tant que le niveau actuel n'est pas complet. Le terme désignant ce type d'arbre est "arbre complet". Cette propriété de l'arbre permet de l'implémenter en utilisant un tableau. Pour un noeud à l'indice n et un arbre binaire, l'enfant gauche de ce noeud se trouve à l'indice 2*n+1 et l'enfant droit à l'indice 2*n+2 (on suppose ici que l'indice du premier élement du tableau est l'indice 0).

J'espère que cette petite explication éclairera quelque personne sur le fonctionnement de cette pile.

Pour ceux que l'anglais ne rebutte pas: http://www.cs.auckland.ac.nz/software/AlgAnim/heaps.html
Explication avec des schémas surtout (je ne me suis pas risqué à essayer de faire des dessins en ascii dans le réponse :p)

Commentaire de manumouton le 27/04/2006 00:15:04

Salut, je suis également entrain de développer un projet basé sur dijkstra et je l'ai implémenté avec un heap également... mais la, je suis calé :-( pourrais tu m'envoyer ton projet de réseau stp ? thx
manumouton@hotmail.com

Commentaire de arnolefou le 07/03/2007 11:50:16

Hello,
Si ça ne dérange personne, j'aimerais pour ma part avoir juste un petit exemple permettant de tester la libraire. J'ai un peu de mal à lire et à comprendre le code pour le moment (malgré les commentaires).
Toute aide est bienvenue.
Merci.

(mon mail kawamasta -at- gmail -dot- com

Commentaire de krikoo le 12/12/2007 20:16:47

bonsoir, serait -il possible d'avoir le code complet du projet réseau.
Je vous remercie par avance.
ap_94@hotmail.fr

Commentaire de chreks le 09/02/2008 21:09:25

Bonsoir,

je travaille sur un projet de réseau lyonnais, avec un algo de Dijkstra, et j'aimerais pour ma part avoir le projet complet.
merci beaucoup.

mon mail : aminechreks@hotmail.fr

Commentaire de zorothehunter le 20/10/2008 15:46:03

mon adresse mail est : mami.barca@hotmail.com

Commentaire de ghaza486 le 22/03/2009 15:09:04

salam
je travaille sur un  projet reseau et j'aimerie que tu m'envoie le contenue de projet
mon email imane8DZ@hotmail.com
slv
demande uregent

Commentaire de ghaza486 le 24/03/2009 13:19:26

meci pour l'aide

Commentaire de maracuja54 le 14/05/2009 16:43:21

Bonjour,

Je suis également intéressé par le dossier complet de ce projet.
Pourriez vous m'envoyez le dossier à cette adresse tuperman@hotmail.fr
Merci beaucoup pour ton aide!!

Commentaire de Bel0 le 14/10/2009 23:02:47

La version de java à utiliser est bien la 1.6. Par contre, il faut que tu charges les librairies xml xerces et xalan. C'est de là que provient ton exception. Google est ton ami pour les trouver.

Commentaire de kimomenna le 07/04/2010 10:52:38

bjr a toussssssss,
mon pfe est determiner le plus cours chemin sur ls rex sdh avec l'algorithme sdh,svp pouvez vous m'aider?? et merci bcp.

Commentaire de Bel0 le 21/04/2010 16:12:20

Les sources est mise à jour avec la suppression de la dépendance XML et l'ajout d'une interface graphique.

Commentaire de Bel0 le 21/05/2010 00:07:51

Le code complet est dans le zip !