Dijkstra : Sommet et Arêtes parcouru
Bonjour,
Dans le cadre de mes études, je travaille sur un programme Java sur le métro parisien.
Le but du programme est d'indiquer les changements pour aller d'un point à un autre.
J'ai donc 3 classes : arret, ligne (tableau d'arret), reseau(tableau de ligne).
Dans la classe reseau, j'ai crée une matrice d'incidence du graphe reseau.
Puis a partir de cette matrice d'incidence j'ai crée une matrice simplifié qui reprend les chemins direct les plus courts entre chaque station. A partir de là j'ai mis en place dijkstra qui me donne donc les distance les plus courts entre chaque station direct ou indirect. Et maintenant j'essaye d'obtenir les arrêts de changements et les lignes.
J'ai donc bien essayer de mettre en place une liste et de récupérer les arrêts de changements, mais j'ai du mal la placer, vu qu'elle me donne soit n'importe quoi, soit rien (et de temps en temps, la bonne réponse mais c'est du hasard a mon avis...). J'ai aussi essayer pour les lignes mais là non plus je ne sais pas où les placeer. Ci-dessous le code de mon dijkstraArret()
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
| public int[][][] DijkstraArret(){
double [][][] cost = unGrapheSimpleTemps();
int[][][] res = new int[cost.length][cost.length][];
LinkedList<Integer> liste = new LinkedList<Integer>();
boolean [] trouve = new boolean [cost.length];
double [] distance = new double [cost.length];
for(int s=0; s<cost.length; s++){
for (int i=0; i< cost.length; i++){
trouve[i]= false;
distance[i] = cost[s][i][0];
}
trouve[s] = true;
distance[s]=0;
for (int i=0; i< cost.length-1; i++){
double minimum=999;
int u=-1;
for(int j=0; j < cost.length; j++){
if(distance[j] < minimum && !trouve[j]){
minimum = distance[j];
u=j;
}
}
trouve[u] = true;
liste.addFirst(u);
for (int w=0; w<cost.length; w++){
if(!trouve[w] && distance[u]+cost[u][w][0]< distance[w]){
distance[w]= distance[u]+cost[u][w][0];
}
}
int compteur=0;
LinkedList<Integer> temp = new LinkedList<Integer>();
while(!(liste.isEmpty())){
temp.add(liste.pollFirst());
compteur++;
}
int[] tab= new int[compteur];
for (int k=0;k<tab.length;k++){
tab[k]=temp.getFirst();
temp.removeFirst();
}
res[s][i]=tab;
}
}
return res;
} |
