begin process at 2012 02 10 19:20:39
  Trouver un code source :
 
dans
 
Accueil > 

Code

 > 

Maths et Algorithmes

 > GRAPHE ORIENTÉ ET DIJKSTRA

GRAPHE ORIENTÉ ET DIJKSTRA


 Information sur la source

Note :
6 / 10 - par 1 personne
6,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Maths et Algorithmes Classé sous :graphe, dijkstra, MouseListener Niveau :Initié Date de création :27/03/2005 Date de mise à jour :27/04/2010 16:59:23 Vu / téléchargé :30 560 / 4 550

Auteur : Bel0

Ecrire un message privé
Commentaire sur cette source (43)
Ajouter un commentaire et/ou une note

 Description

Cliquez pour voir la capture en taille normale
Le but premier de ce code est d'implémenter un graphe par la méthode des "incidence list" ainsi que l'algorithme de Dijkstra. Ce code a été écrit dans le cadre d'un projet de réseau. Il permet de trouver le chemin le plus court à travers une série de router mais il peut (normalement) s'adapter à n'importe quelle situation. Si vous avez des questions, commentaires à propos de ce code, n'hésitez pas à poster !

MAJ 30/06/2007:
J'ai reçu pas mal de mails me demandant de fournir un exemple utilisant Dijkstra et le graphe.
Modifications:
- Ajout d'un fichier Demo.java qui montre comment utiliser le graphe et récupérer le chemin le plus court;
- Utilisation de Xerces+Xalan pour récupérer les données du graphe (C'est tellement plus facile avec XPath :));
- Modification de certaines classes pour les rendre génériques.
Il n'y a pas d'interface graphique. La seule raison est que je ne suis vraiment pas doué pour ça :P



 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip


 Historique

30 juin 2007 18:19:43 :
Maj 30/06/2007
21 avril 2010 16:11:04 :
MAJ 21/04/2010: Je vois dans les commentaires que beaucoup de gens n'arrivent pas à faire fonctionner la démo à cause de la librairie XML. J'ai donc décidé de modifier la source pour y faire les modifications suivantes: retrait de la dépendance de la librairie xml, ajout d'une interface graphique avec les particularités suivantes: - Le noeud initial est coloré en vert - Le chemin le plus court est dessiné en rouge - Les autres chemins sont affichés en blanc - La distance par rapport au noeud initiale est affichée pour chaque vertex - Charge les données à partir d'un fichier (3 exemples inclus) - Les placements initiales des noeuds est aléatoire ce qui rend le graphe fort peu lisible. Vous avez donc la possibilité de déplacer chaque vertex où bon vous sembles (Veillez à bien cliquer à l'INTERIEUR du rond) Si des remarques, n'hésitez pas à les faire dans les commentaires.
27 avril 2010 16:59:24 :
Correction orthographe

 Sources du même auteur

Source avec Zip MINI-COMPILATEUR

 Sources de la même categorie

IMPLÉMENTATION DE L'ENSEMBLE C AVEC JAVA par Scupper
CALCUL D'EXPONENTIEL ( PRÉCISION MODIFIABLE) par Scupper
Source avec Zip TRANSFORMATION D'UNE EXPRESSION ARITHMETIQUE (INFIXÉ) EN POS... par billatosco
PROBLÈME DES N-REINES par jojolemariole
Source avec Zip ARRAYMATRIX -MATRICE MULTIDIMENSIONELLE ET GÉNÉRIQUE- , IMP... par labandus

 Sources en rapport avec celle ci

Source avec Zip Source avec une capture COLORATION DE GRAPHE par ynabid
Source avec Zip Source avec une capture EDITEUR DE COURBES par jojolemariole
Source avec Zip TYPE DE DONNÉES ABSTRAIT GRAPHE par smutsonberg
Source avec Zip Source avec une capture ANIMATION DANS UN JPANEL + SURVEILLANCE DE LA SOURIS ET DU C... par pyo656
Source avec Zip Source avec une capture INTERFACE BILINGUE POUR LA GESTION DU MONDE DES ANIMAUX par y_program

Commentaires et avis

Commentaire de Arnold59 le 25/04/2005 11:35:13

Quelle applet faut-il créer pour lancer les programmes

Tous les pogs ont été compiler correctement sous l'environnement SDK 1.4

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 didier045 le 04/05/2005 11:53:59

je fait un projet sur le metro parisien et il serait aimable a toi de m envoyer par mail le projet reseau complet
mon mail: didier045@hotmail.com
merci d'avance

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 trypon le 10/10/2005 22:00:12

Moi aussi je serais interressé par le code de ce projet reseau...
merci d'avance.
tryp@hotmail.com

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 benoitt76 le 14/11/2005 13:03:39

De même, je serais intéressé par le code complet du projet réseau... si c'est possible !
nono_78310@hotmail.com

Merci d'avance.

++

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 Davecpp le 16/11/2005 12:19:27

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

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 marie1983 le 23/11/2005 00:36:23

De meme, tu pourrai m'envoyer le code complet,stp.
tangxueyan2000@hotmail.com

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 NoModoTuXVengeurMasked le 23/11/2005 19:02:28

Bonjour.
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 :)

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 ivan76 le 21/02/2006 12:27:19

j'ai fini mon projet sur le calcul du plus court chmin dans le metro parisien. si ça intéresse : adslfx@hotmail.fr

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 dj leemon le 28/02/2006 22:46:11

Bonjour!

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é!

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 fugeo le 10/04/2006 17:54:29

je serai ravi de recvoir aussi le code complet.
merci!
fugeo@voila.fr

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 MadCat81 le 08/05/2006 17:39:45

Je viens de charger ton code et le trouve interessant!

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)

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 selim le 22/06/2007 01:49:48

bonsoir,

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

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 redoua007 le 21/12/2007 22:34:50

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

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:36:58

je vois que je suis venus un peu en retard là mais bon si quelqu'un pourra m'aider svp, en fait je travaille sur un projet ou je doit utiliser Djikstra pour trouver le chemins le plus cours entre des carrfours, j ai essayé d utiliser ce code mais il compile pas ( y a un pb avec le XPathAPI il me demande de creer une class XPathAPI et vu que je suis debutant ( tres mm) je sais pas comment faire) merci d avance

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

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

Commentaire de ghaza486 le 17/03/2009 09:14:30

salam
je suis sur un projet réseau et j'aimerais que tu m'envoies tout le contnue du projet réseau à:
merci

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 Bel0 le 23/03/2009 18:12:00

30 commentaires et 7 liés à la source (sans compter mes messages). Il serait temps de commenter ce qui est posté (merci à ceux qui se sont intéressés à cette source d'ailleurs !).

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.

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

meci pour l'aide

Commentaire de flo0011 le 14/05/2009 11:47:00

Bonjour,

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

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 bimen le 10/10/2009 11:30:37

Salut tout le monde,
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.

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 bimen le 15/10/2009 17:53:01

Salut,
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. :(

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 kimomenna le 07/04/2010 10:56:53

désolé svp,
j'uoblié d'écrire le nom d'algorithe c'est dijkestra,merci

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 amineouazzani le 27/04/2010 11:50:57

puis je avoir le code complet svp
merci amine_ouazzani@yahoo.fr

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

Le code complet est dans le zip !

Commentaire de bibo6300 le 22/11/2010 22:37:35

hi. i m a new member and i have a Q about the source :
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

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

Implantation d'algorithme de Dijkstra en C/C++ [ par asrml ] Bonjour à tous, vous pourriez m'aider s'il vous plait pour une question suivante:comment implater l'algorithme de dijkstra"la recherche du plus court represention graphique d'un graphe [ par manou74 ] bonjour tt le monde; à partir des 2 matrices de poste-condition et pré-condition d'un réseau de pétri je veux dessiner le graphe correspondant à ce ré test si un graphe est connexe [ par rawasibasma ] Bonjour svp est ce qu'il y a quelqu'un qui peut m'aider j'ai une matrice d'incidence d'un graphe est j'ai besoin d'une algoritheme qui test si ce gra theorie de graphe [ par djamafrancki ] bonjour, enfaite je suis etudiant en 3em annee miage et j fais comme matiere theorie de graphe pour cela le professeur , a donnee comme projet a soute module pour dessiner graphe de reseau de petri [ par manou74 ] bonjour; j'ai une application à developper pour le projet de fin d'etude,elle est basée sur les reseaux de petri,mon probleme est que je dois represen [BAR]creation d'un graphe [ par redvella ] salut tous le monde, pouvez_vous m'aidez pour écrire une fonction en matlab qui permet de saisir un graphe ( sommets , arcs et valuations) juste donn demande code simple de lalgorithme de dijkstra en java avec interface graphique [ par ayachesouhail ] svp qui peut me donner le code de l'algorithme de dijkstra avec de simples classes et en implémentant une interface graphique merci d'avance projet RMI + algorithme dijkstra [ par soregh ] bonjour, j'ai travaillé pendant 2 semaine sur un projet se basant sur RMI pour executer l'algorithme de dijkstra avec quelques interfaces graphiques selectionner avec clavier uneJList [ par profiter ] bonjour, je travaille avec une JList pour detecter les selections j'utilise : [code=java] MouseListener mouseListener = new MouseAdapter() { [clos] algorithm de dijkstra's [ par metalfish ] Bonjour, SVP, y a t il quelqu'un qui peut m 'aider. je veux un algorithme de dijkstra's en java pour les graph non orientés merci d'avance


Nos sponsors


Sondage...

CalendriCode

Février 2012
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
272829    

Consulter la suite du CalendriCode

 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 0,421 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales