Dijkstra Java Code

Version imprimable

18/04/2012, 11h50
JohnKr

Dijkstra Java Code

Bonjour,

Je viens d'étudier les graphes et je recherche, actuellement, le code Java de l'algorithme de Dijkstra.
J'ai déjà recherché sur Internet.
Toutefois, le code est souvent présenté sous forme de matrice d'adjacence et avec des paramètres différents (un sommet de départ et un d'arrivée). Ce qui est assez déroutant (je ne connais pas encore ce genre de matrice)

En fait, j'ai besoin d'une méthode qui s'appuie sur les listes d'adjacence et qui n'utilise qu'un seul paramètre : le sommet de départ.
A partir de là, la méthode renvoie tous les chemins les plus court vers les autres sommets.

Pouvez vous m'aider ?
Merci d'avance.
18/04/2012, 13h34
Népomucène

as-tu regardé :
http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

Après la description avec un exemple concret, il y a un pseudo-code (en français) qu'il est facile de ré-écrire en java

Bonjour,

Cela fait déjà un petit moment que j'ai regardé le pseudo code sur Wikipédia,
j'ai toujours du mal quant à l'implantation de mon programme.

Pouvez vous m'orienter ?

Ma structure de donnée, imposée au départ, se présente ainsi :
Une classe graphe, une classe ListAd (qui permet de créer des Listes d'adjacences ), Element (qui est défini par un sommet et une distance).

Je dois utiliser 2 vecteurs (Vector) qui contiennent des Elements : T et V.
T représente l'ensemble des noeuds et V le Vecteur solution contenant le chemin le plus court.
En parcourant l'ensemble de mon circuit, je dois supprimer au fur et à mesure les Elements de D et les rajouter dans le vecteur solutions.

Où j'en suis :
1) La phase d'initiation (0 et infini) est faite
2)...
3)La partie sur la suppression des éléments de D et l'ajout dans S est faite
4) L'actualisation des distances est faite

Je bloque sur l'étape 2 : la recherche du plus petit noeud suivant.

Voici ce que je pensais faire :
Code:

1 2 3 4 5 6 7 while(ListAd[numero_sommet]!=null){ if (tmp>ListAd[numero_sommet].valeur){ tmp=ListAd[numero_sommet].valeur; index_mini=numero_sommet;//ici je repère l'indice pour lequel la distance est la plus faible } ListAd[numero_sommet]=ListAd[numero_sommet].prochain // Je regarde les prochains noeuds dans la liste d'adjacence pour voir s'il n'y a pas de nouveaux noeuds.
Après réflexion j'ai peur que ce code soit faux.
Avec cette instruction,
ListAd[numero_sommet]=ListAd[numero_sommet].prochain.Est ce que numero_sommet prend la valeur du sommet suivant ?

2ème problème, imaginons je considère un noeud. Donc par cette méthode, je parcours tous les prochains noeuds pour évaluer la distance. Je l'ai trouvé. D'accord, maintenant, j'opère sur ce nouveau noeud. N'y aura t-il pas un problème ? Car lors de l'évaluation du premier noeud, je l'ai parcouru jusqu'à ListAd[numero_sommet]=null. Donc, maintenant, ListAd[numero_sommet]=null, non ?

Merci d'avance pour votre aide.

03/05/2012, 22h02
Mathieu_2705

Salut JohnKr,

Pour ma part, j'ai utilisé des piles, de cette façon, tu n'auras pas à gérer les indices de tableaux.
En ce qui concerne l'étape deux, à partir du sommet courant, tu regardes toutes les arrêtes qu'il possède et tu ajoute cette distance à la précedente, s'il n'a pas était marqué, sinon tu empile la dernière valeur de la pile.

Bon courage!

Cordialement
03/05/2012, 22h56
JohnKr

Bonsoir,

Merci d'avoir répondu.
J'ai du mal à voir.
Quand vous parlez de pile, vous voulez dire que je dois passer en récursif ?

Merci encore
04/05/2012, 21h59
Mathieu_2705

Bonsoir,

Non, l'utilisation de piles n'oblige pas le récursif, ça permet simplement de ne pas avoir à gérer les indices de tableaux.

Brièvement l'étape deux donne quelque chose dans ce genre, pour chaque sommet relié à une arête du sommet courant, calcule la distance.
Sommer cette distance à la valeur du sommet courant et l'empiler dans la pile du sommet (pas celle du sommet courant).

Pour l'initialisation de cette étape, le sommet courant correspond au sommet de départ.

Le plus simple, c'est de faire un exemple simple sur papier, ensuite le code sera plus claire.

J'espère avoir était assez claire dans mes explications,

Cordialement
08/05/2012, 15h31
JohnKr

Bonjour,

Merci de votre aide.
C'est vrai que cela serait pratique si je n'avais pas à gérer les indices.
En fait, je ne connais l'utilisation de la pile que par rapport à la récursivité.
Donc quand vous dîtes "'empiler dans la pile ", comment dois je m'y prendre ? Je veux dire il n'y a pas de fonction spécifique pour empiler, non ?

Merci encore

Bonjour,

Pour utiliser une pile, il existe des méthodes pour empiler et dépiler :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
                Stack<Integer> pile = new Stack<Integer>();
		pile.push(1);
		pile.push(2);
		pile.push(3);
 
		String chaine = "";
 
		while(!pile.isEmpty()){
			chaine = pile.pop() + ", "+chaine;
		}
 
		System.out.println("pile : " + chaine);

Cordialement,
Mathieu_2705

19/05/2012, 09h02
JohnKr

Bonjour,

Merci pour cette exemple, je pense que c'est plus clair pour moi maintenant en ce qui concerne la pile.

Citation:

Brièvement l'étape deux donne quelque chose dans ce genre, pour chaque sommet relié à une arête du sommet courant, calcule la distance.
Sommer cette distance à la valeur du sommet courant et l'empiler dans la pile du sommet (pas celle du sommet courant).

Est ce que cela veut dire que je dois créer une pile spécifique à chaque sommet ?

Merci encore de votre aide
19/05/2012, 19h37
Mathieu_2705

Bonjour,

Oui, c'est comme ça que je l'ai réalisé. Peut être existe t'il d'autre moyen. Voici l'exemple avec lequel j'ai réalisé l'algorithme, il se trouve dans le dossier Maths du site :

http://www.partagedecours.hebergratu...hp?dir=partage

Le refaire à la main pourrai vous aider à comprendre pourquoi une pile, et à trouver un algorithme.

Cordialement,
Mathieu_2705