implementation du dijkstra en java

Version imprimable

Voir 40 message(s) de cette discussion en une page

22/01/2008, 16h44
rafikindia

implementation du dijkstra en java

bonjour,

Je voudrais dévellopez un appli en java qui appliquerez l'algorithme de Dijkstra.
Je ne suis pas douée en interface graphique.
Donc j'ai choisi de récuperer les infos du graphes à partir d'un fichier texte(avec buffer reader et Stringtokenizer).

Je voudrais savoir comment je fais pour récuperé ces infos en tant que noeuds et arretes et son point.

Merci d'avance
22/01/2008, 18h16
CyberChouan

StringTokenizer est une très vieille classe, qui est assez lourde à manier.
Pour le parsing de ton fichier, je te conseille vivement de passer à la méthode "split()" de la classe String.

Concernant ton problème principal par contre, je ne connais pas très bien cet algorithme et je ne voudrais pas d'induire en erreur.
25/01/2008, 14h50
rafikindia

Merci

Je crois qu'il serait mieux que je récupère les données des graphes à partir d'un fichier XML.

Mais je suis en train de cherché une meilleur exemple qui m'expliqerai comment récupérer les données à partir d'un fichier XML.
25/01/2008, 16h36
CyberChouan

Tu trouveras ça dans la FAQ du site... le parsing XML étant quelque chose de très classique.
25/01/2008, 17h53
T`lash

Par contre, es-tu sûr que Dijkstra est la bonne solution ?

Cet algo va te donner le chemin optimal mais la consommation en ressources va augmenter de manière exponentielle avec le nombre de sommets à ton graphe.

Le A* fournit une solution moins optimale mais dans un temps inférieur.

À toi de voir si le chemin doit réellement être le plus court ou l'un des plus courts.
26/01/2008, 10h09
leyee

Je suis tout a fait d'accord mais il s'agit tres certainement d'un projet d'étude ... Il est clair que l'A* est à la fois plus performant et plus passionnat à developper et à optimiser à l'aide d'heuristiques sur les distances
26/01/2008, 10h48
millie
Dis nous comment tu comptes enregistrer ton graphe, car il y a plusieurs stratégies, et du xml n'est pas forcement utile

par exemple, un fichier décrivant uniquement les sommets et les arcs peut être suffisant
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 Sommets: A B C D E F Arcs: A B C B E F A E
Et pas forcement besoin de passer par du xml
26/01/2008, 16h09
rafikindia

Je suis aussi d'accord. En effet je suis en train de faire ce programme pour un projet d'école.
J'ai choisi Dijkstra car c'est un des algorithmes que je dois présenter.
Je suis aussi d'accord pour le parsing de XML, j'hésite toujours pour ca.

Au début je voulais récupérer les infos du graphes à partir d'un .txt mais le problème c'est que je sais pas comment récuperer ses données.

"Je suis trés content que vous me reépondez tout de suite", je croyais pas que j'allais obtenir des conseils aussi vite que ca.
26/01/2008, 16h11
millie

Avant de savoir comment récupérer les données du fichier texte, il faudrait que tu définisses formellement comment ils vont être présentés.
26/01/2008, 16h18
rafikindia

Je voudrais présenter mon graphe de la facon suivante dans un fichier .txt :

Noeud départ, Noeud d'arrivé, distance
Noeud départ2, Noeud d'arrivé2, distance2
...
...
....

Maintenant mon souci, c'est comment je vais récupérer ces données et comment faire voir qu'un sommet j et j' sont adjacent au sommet i

merci enconre
26/01/2008, 18h00
T`lash

Tu prends le tout à l'envers ; dans ton fichier tu dois avoir tes arêtes (si tous tes sommets sont reliés entre eux pas besoin de les déclarer à part).

Tu calculeras les distances dans ton algo.

Par contre, ton graphe est-il orienté ?
26/01/2008, 23h08
rafikindia

oui mon graphe est orinté
27/01/2008, 00h01
T`lash
Tu peux créer un fichier de ce type :
Code:

1 2 3 4 5 6 7 A=>B,C,E; B=>A,C,D; C=>; D=>B,C; E=>A; F=>D; G=>;
Tu déclares ainsi tous tes sommets ainsi que tes arêtes orientées et tu gères mêmes les sommets "orphelins".

Ton programme va lire ce fichier et construire le graphe puis calculer les distances tout comme les chemins.
28/01/2008, 09h58
rafikindia

merci,

comment je fais pour récupérer ses données?

Tu me diras si ça fonctionne :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.ArrayList;
 
public class Sommet {
 
    /**
     * Ensemble des sommets d'où partent une arête ayant pour arrivée l'instance courante de la classe Sommet.
     */
    private ArrayList<Sommet> entrants = new ArrayList<Sommet>();
    /**
     * Ensemble des sommets d'où arrivent une arête ayant pour départ l'instance courante de la classe Sommet.
     */
    private ArrayList<Sommet> sortants = new ArrayList<Sommet>();
 
    /**
     * Crée une arête partant de l'instance courante de la classe Sommet et arrivant au sommet dest.
     * Une arête est connue des deux sommets qu'il rejoint.
     * @return l'instance courante de la classe Sommet.
     */
    public Sommet ajouterSortant(Sommet dest) {
        this.sortants.add(dest);
        dest.entrants.add(this);
        return this;
    }
 
    /**
     * Renvoie une COPIE de la collection de sommets entrants.
     */
    public ArrayList<Sommet> getEntrants() {
        return (ArrayList<Sommet>)this.entrants.clone();
    }
 
    /**
     * Renvoie une COPIE de la collection de sommets sortants.
     */
    public ArrayList<Sommet> getSortants() {
        return (ArrayList<Sommet>)this.sortants.clone();
    }
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
 
public class LectureGraphe {
 
    public static void main(String[] args) {
        String cheminFichier = "";
 
        HashMap<String, Sommet> sommets = new HashMap<String, Sommet>();
        HashMap<String, String> aretes = new HashMap<String, String>();
 
        String regex = "^(\\w+)=>(.*);";
        java.util.regex.Pattern pattern = java.util.regex.Pattern.compile(regex);
        java.util.regex.Matcher matcher;
 
        // On lit le fichier et on crée tous les sommets.
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(cheminFichier)));
            String ligne;
            while ((ligne = br.readLine()) != null) {
                matcher = pattern.matcher(ligne);
                if (matcher.find()) {
                    sommets.put(matcher.group(1), new Sommet());
                    aretes.put(matcher.group(1), matcher.group(2));
                }
            }
            br.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
 
        // On relie les sommets entre eux en ajoutant les arêtes au graphe.
        Set<Map.Entry<String, Sommet>> listeSommets = sommets.entrySet();
        for (Map.Entry<String, Sommet> sommetEntry : listeSommets){
            for (String dest : aretes.get(sommetEntry.getKey()).split(",")){
                Sommet destination;
                if ((destination = sommets.get(dest)) != null){
                    sommetEntry.getValue().ajouterSortant(destination);
                }
            }
        }
    }
}

Tu peux par la suite faire tous tes calculs sur le HashMap sommets.
J'espère ne pas avoir fait ça de façon trop bourrin ; les programmeurs confirmés me corrigeront peut-être.

30/01/2008, 14h52
rafikindia

Merci infiniment.

Entre temps, j'ai commencé à faire le programme avec les tableaux et je crois que g bientot fini. Je posterai mon programme dés que je l'aurai finalisé.

Merci enconre pour ton aide, je suis dégouté de ne pas l'avoir vu bien avant.
30/01/2008, 15h00
T`lash

Citation:

Envoyé par rafikindia

Merci infiniment.

Entre temps, j'ai commencé à faire le programme avec les tableaux et je crois que g bientot fini. Je posterai mon programme dés que je l'aurai finalisé.

Merci enconre pour ton aide, je suis dégouté de ne pas l'avoir vu bien avant.

Et tu as choisi quelle approche pour la récupération des données ?
19/02/2008, 14h21
emy_1985

Bonjour, moi aussi j'ai besoin d'implémenter l'algo de dijkstra, pour un projet de fin d'étude genre mappy. Donc j'ai des adresses que je récupère d'un fichier plat, je l'ai insère dans ma BD, puis je dois faire mes calcules la dessus en les comparant avec un base d'adresse dèja prédéfinie.

Mon problème c'est comment définir les nœuds de mon graphe par rapport à mes adresses???

N.B : Je viens de trouver une class prédéfinie dans java :

SSF.OS.OSPF
Class Dijkstra

java.lang.Object
|
+--SSF.OS.OSPF.Dijkstra

alors est ce que j'utilise une instance de cette class, ou je monte à la main mon algo?? (la méthode la plus facile et la plus rapide).

Merci
19/02/2008, 17h58
T`lash

Citation:

Envoyé par emy_1985

Bonjour, moi aussi j'ai besoin d'implémenter l'algo de dijkstra, pour un projet de fin d'étude genre mappy. Donc j'ai des adresses que je récupère d'un fichier plat, je l'ai insère dans ma BD, puis je dois faire mes calcules la dessus en les comparant avec un base d'adresse dèja prédéfinie.

Mon problème c'est comment définir les nœuds de mon graphe par rapport à mes adresses???

N.B : Je viens de trouver une class prédéfinie dans java :

SSF.OS.OSPF
Class Dijkstra

java.lang.Object
|
+--SSF.OS.OSPF.Dijkstra

alors est ce que j'utilise une instance de cette class, ou je monte à la main mon algo?? (la méthode la plus facile et la plus rapide).

Merci

Je ne sais pas si je pourrais réellement t'être d'un grand secours, mais je pense que tu pourrais utiliser chaque carrefour comme un nœud.
Une adresse est repérée en premier lieu par le tronçon d'axe routier sur lequel elle se situe (les deux carrefours les plus proches).
Ton algorithme devras rechercher le plus proche des deux puis tu parferas ton résultat par la position de l'adresse sur l'arête.

Il existe certainement une meilleure approche mais je ne suis pas un pro de la résolution de chemins (je séchais les cours d'algo des graphes à la fac....).

Par contre, je ne crois pas qu'il te faille implémenter Dijkstra, mais plutôt A* car il te faut prendre en compte le type d'axe (route communale limité à 50km, voie rapide, autoroute, ...), sa longueur, etc....
Si tu veux vraiment pousser les choses il faut aussi prendre en compte les piétons et les vélos qui ont accès à des voies différentes et ne peuvent en empreinter d'autres. Tout ceci à des vitesses différentes.

Je ne connais pas les API qui pourraient aider à l'implémentation des algorithmes de résolution de chemins, mais je pense qu'il est mieux de tout faire soi-même car, dans le fond, Dijkstra et A* ne sont pas si complexe qu'il n'y paraissent ; les parties plus complexes de ces algorithmes sont les parties spécifiques et donc celles qu'il faut de toute manière coder.

LE CODE

Bonjour a ts,

voici comme je vous ai prévenu je vous met le code que g devellopé.
Ce code ne contient pas d'interface graphique, J'ai fai ce ke g pu.
Mais l'essentiel c'est que ca marche.

Le graphe doit etre rentré manuellement par l'utilisateur dans la class main du programme. Je vous ai cité une exemple. Encore merci infiniment à ts ki m ont aidé.:yaisse2::yaisse2::yaisse2:
==========================================================

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
public class InputGraph {
 
	 public int [][] arc;       // Matrice d'adjacense
     public Object [] sommet;   //objet sommet    
 
     public static int count;
 
   public InputGraph (int n){
       arc = new int[n][n];
       sommet = new Object[n];
 
   }
public int GetSize (){			// récupère la taille du sommet
   return sommet.length;
 
}
 
public void SetSommet(int node, Object label){		//permet d'ajouter un sommet   
  sommet[node]=label;
 
}
 
public Object GetSommet(int node){		// récupère la valeur d'un sommet
  return sommet[node];
 
}
 
 
public void AddArc(int SommetDep, int SommetArr, int dist){		// ajoute un arc
  arc [SommetDep][SommetArr]=dist;
 
}
 
public int GetPoids(int SommetDep, int SommetArr){			//récupère la distance
  return arc [SommetDep][SommetArr];
 
}
 
 
 
 
public void AfficheMatrice(){						//affiche la matrice du graphe
 
  for (int j = 0; j < arc.length; j++) {
	  System.out.println("");
      System.out.println( " DE " + sommet[j] +" jusqu'à ");
      System.out.println("");
  for (int i = 0; i < arc[j].length; i++) {
      if (arc[j][i]>0) 
      System.out.println(sommet[i] + " la distance est de " +arc[j][i] );
      }
  }
 
}
public  int [] ChercheVoisin(int node){				//construit un tableau des sommets adjacents d'un sommet 
 
  count=0;
 
  for (int i = 0; i < arc[node].length; i++) {
      if (arc[node][i]>0 ) {count ++; }
  }
      final int[]rep = new int [count];      
 
  count=0;    
  for (int i = 0; i < arc[node].length; i++){
       if(arc[node][i]>0){rep[count++]=i;}        
  }     
  return rep;
}
 
public static void main(String[] args) {
 
  InputGraph ex = new InputGraph (4);
  ex.SetSommet(0, "New york");
  ex.SetSommet(1, "Paris");
  ex.SetSommet(2, "Londres");
  ex.SetSommet(3, "New delhi");
  ex.AddArc(0, 1, 400);
  ex.AddArc(0, 2, 200);
  ex.AddArc(1, 2, 300);
  ex.AddArc(2, 1, 100);
  ex.AddArc(1, 3, 100);
  ex.AddArc(2, 3, 500);
  ex.AddArc(2, 0, 200);
 
  ex.AfficheMatrice();
  System.out.println("");
  System.out.println("Les plus court chemin à partir du sommet source sont :");
 
  final int [] pred = Dijkstra.djikstra(ex, 0);
  for (int n = 0; n < 4; n++) {
 
  Dijkstra.AfficheChemin(ex,pred, 0, n);
  } 
}
}
==========================================================
 
public class Dijkstra {
 
 
    public static int [] djikstra (InputGraph IG, int Source){
 
        final int [] distancecc = new int [IG.GetSize()];
        final int [] pred = new int [IG.GetSize()];
        final boolean [] marque = new boolean [IG.GetSize()];
 
        for (int i = 0; i < distancecc.length; i++) {
            distancecc[i]=Integer.MAX_VALUE;
            }
        distancecc[Source]=0;
 
        for (int i = 0; i < distancecc.length; i++) {
 
            final int U= ExtraireMin.ExtraireMin (distancecc, marque);
            marque[U]=true;
 
            final int [] V= IG.ChercheVoisin(U);
            for (int j = 0; j < V.length; j++) {
                final int NV = V [j];
                final int d = distancecc[U] + IG.GetPoids(U, NV);
                if (d < distancecc[NV]) {
                    distancecc[NV]=d;
                    pred[NV]=U;
                   }
            }
 
         }
 
        return pred;
 
    }
 
    public static void AfficheChemin (InputGraph IG, int [] pred, int source, int n){
 
 
        LinkedList cheminpc =new LinkedList();
 
        int x=n;
        while (x!=source){
            cheminpc.add(source, IG.GetSommet(x)+"=====>");
            x=pred[x];    
        }
        cheminpc.add(source, IG.GetSommet(source)+"=====>");
 
        System.out.println("--------------------------------------------");
        System.out.println(cheminpc);
 
    }
}
==========================================================
public class ExtraireMin {
 
	public static int ExtraireMin(int [] distancecc, boolean [] marque){
        int x =Integer.MAX_VALUE; 
        int y=0;
 
        for (int i = 0; i < distancecc.length; i++) {
             if (!marque[i] && distancecc[i]< x) {
 
                y=i;
                x=distancecc[i];
 
            }
 
        }      
 
        return y;
    }
 }

Voir 40 message(s) de cette discussion en une page