GRAPHE ORIENTÉ ET DIJKSTRA
cs_Arnold59
Messages postés
50
Date d'inscription
lundi 8 mars 2004
Statut
Membre
Dernière intervention
3 mars 2009
-
25 avril 2005 à 11:35
Saoudi89 Messages postés 2 Date d'inscription mardi 20 mars 2012 Statut Membre Dernière intervention 27 août 2013 - 23 mars 2012 à 10:59
Saoudi89 Messages postés 2 Date d'inscription mardi 20 mars 2012 Statut Membre Dernière intervention 27 août 2013 - 23 mars 2012 à 10:59
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/30362-graphe-oriente-et-dijkstra
https://codes-sources.commentcamarche.net/source/30362-graphe-oriente-et-dijkstra
23 mars 2012 à 10:59
votre travail est excellent, je vous encourage.
J'ai l'idée de améliorer l'algorithme de Dijkstra de cette façon:
* Donner l’arborescence de départ obtenu en appliquant Dijkstra avec les valeurs de p(x) pour tout
sommet x.
* Donner l’arborescence des plus courts chemins quand elle existe ainsi les valeurs de p(x) et dans le cas contraire, de détecter un circuit absorbant en indiquant sa longueur.
Ainsi on gagne le cout du temps d'exécution.
Qui peut m'aider à implémenter l'amélioration car je suis faible en java :(
Merci d'avance
1 mars 2012 à 14:59
Merci par avance
22 nov. 2010 à 22:37
i wont to controle the place or the position of noud for making a graph +++ readble(lisible)
who i can do that ..thnx for you help
21 mai 2010 à 00:07
27 avril 2010 à 11:50
merci amine_ouazzani@yahoo.fr
21 avril 2010 à 16:12
7 avril 2010 à 10:56
j'uoblié d'écrire le nom d'algorithe c'est dijkestra,merci
7 avril 2010 à 10:52
mon pfe est determiner le plus cours chemin sur ls rex sdh avec l'algorithme sdh,svp pouvez vous m'aider?? et merci bcp.
15 oct. 2009 à 17:53
Merci bien pour votre réponse. Exactement, la version que j'utilise c'est 1.6 pour les bibliothèques j'ai chargé tte la librairie org et meme je me suis assurrée qu'elle est complète (y compris xerces et xalan) meme "PrefixResolver" qui se trouve dans l'exception
je me suis assurée de son existance. C'est pour celà je suis vraiment bloquée j pas pu résoudre cette exception. :(
14 oct. 2009 à 23:02
10 oct. 2009 à 11:30
je suis interessé par cet algo de dijkstra, malheureusment je pas pu voir le démo. en fait l'execption que j'obtient c'est:
Exception in thread "main" java.lang.NoClassDefFoundError:org/apache/xml/utils/PrefixResolver
bon je travaille avec NetBeans IDE 6.7.1 jre 6 , j trouvé dans un tel forum que je dois mettre le j2re 1.4.2_01 pour que ne pas avoir cette exception or ce dernier n'est pas compatible avec Map<String,Vertex> str2vtx = new HashMap<String,Vertex>(); (ça sera erreur)
svp pouvez vous m'aider?? et merci bcp.
14 mai 2009 à 16:43
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!!
14 mai 2009 à 11:47
Etudiant en ecole d'ingénieur, je dois concevoir un reseau de metro pour obtenir le plus court chemein nentre 2 ligne de stations!!
Pourriez vous m'envoyez le dossie complet à cette adresse floetrom_99@hotmail.com!!
Merci beaucoup pour ton aide!!
24 mars 2009 à 13:19
23 mars 2009 à 18:12
Pour les autres qui cherchent à récupérer le projet réseau afin de l'inclure directement dans leur travail actuel, vous ne l'aurez pas. Je suis fatigué de gens qui essaye de "grater une source qui fera l'affaire". Je ne travaille pas pour vous. Tous commentaires ou messages privés demandant les sources du projet réseau seront ignorés.
22 mars 2009 à 15:09
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
17 mars 2009 à 09:14
je suis sur un projet réseau et j'aimerais que tu m'envoies tout le contnue du projet réseau à:
merci
20 oct. 2008 à 15:46
20 oct. 2008 à 15:36
9 févr. 2008 à 21:09
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
21 déc. 2007 à 22:34
Je vous remercie par avance.
redoua007@gmail.com
12 déc. 2007 à 20:16
Je vous remercie par avance.
ap_94@hotmail.fr
22 juin 2007 à 01:49
est ce que c'est possible svp de m'envoyer la classe qui contient
la fonction main pour tester ce programme.
car j'ai besoin de l'essayer pour comprendre cet algorithme
afin de réviser pour mon examen ce lundi prochain.
merci de votre part ...c'est trés urgent!!!!
mon adresse email : futureman@postmail.ch
7 mars 2007 à 11:50
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
8 mai 2006 à 17:39
J'aimerais bien recevoir le projet reseau complet que tu as fait, j'aimerais en effet approfondir mes connaissances (Java et reseaux)
Merci d'avance ^^ (MadCat34@gmail.com)
27 avril 2006 à 00:15
manumouton@hotmail.com
10 avril 2006 à 17:54
merci!
fugeo@voila.fr
9 avril 2006 à 01:05
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)
28 févr. 2006 à 22:46
Moi je souhaiterais simplement avoir une explication sur une partie du code. Plus précisement sur la gestion de cette PriorityQueue, j'ai du mal à voir comment elle est gérée et la notion de BubbleUp & Down m'echappe.
Pourrais tu m'aider? en laissant un message ici même de telle sorte que tout le monde pourra en profiter. :)
Merci beaucoup pour ton code en tout cas c'est très bien codé!
26 févr. 2006 à 00:06
c klk 1 pe m'aider sa sera un grand plaisir de leur part
bonn courage a tt le monde
21 févr. 2006 à 12:27
19 févr. 2006 à 16:17
mctoufiq@gmail.com
23 nov. 2005 à 19:02
Je suis d'accord avec toi dans l'absolu Julie.
Mais je suis aussi d'avis que dans une école d'ingénieur, tu dois plutôt apprendre à réfléchir par toi même. C'est le but premier de la formation. Je ne pense pas qu'apprendre à piquer les idées des autres et à mettre ton nom dessus soit un bon investisement pour ta vie future :/
Par contre, comprendre comment fonctionne l'algorithme et le ré-implémenter selon nos besoins me semble une meilleure idée.
Et tu ne pouvais pas connaître le passif de plsvse qui s'est toujours arrangé pour profiter du travail des autres sans rien faire en retour (genre sangsue).
Donc voilà. Je suis d'accord avec toi, mais tu apprendras en entreprise plus tard que ce n'est pas toujours vrai, et qu'il faut parfois relativiser dans certains cas :)
23 nov. 2005 à 13:29
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.
23 nov. 2005 à 00:36
tangxueyan2000@hotmail.com
22 nov. 2005 à 23:44
Implémente le, tu apprendra plus de chose. Et puis Bellman-Ford est plus optimisé.
16 nov. 2005 à 12:19
14 nov. 2005 à 18:54
Merci
14 nov. 2005 à 13:03
nono_78310@hotmail.com
Merci d'avance.
++
7 nov. 2005 à 09:41
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.
10 oct. 2005 à 22:00
merci d'avance.
tryp@hotmail.com
23 mai 2005 à 21:04
tiburcedavy@yahoo.fr
avec mes remerciements
4 mai 2005 à 11:53
mon mail: didier045@hotmail.com
merci d'avance
26 avril 2005 à 13:45
25 avril 2005 à 11:35
Tous les pogs ont été compiler correctement sous l'environnement SDK 1.4