Discussion :

[bassim]

Salut,
j'ai développé ,il y a quelques temps, une application permettant de retrouver le chemin le plus court dans un réseau routier en utilisant l'algorithme de Djikstra,
tout ça en respectant un modèle objet. Peut être que ça peut vous interresser :
JGraphe(Sources)

PS: l'exécution du programme nécessite Java 6 !

[emy_1985]

Ben merci beaucoup pour votre aide précieuse. Je crois que j vais faire comme vous avez dit (implémenté dijkstra).

Merci une autre fois et je vous tiens au courant

[Maxbester]

Laissez moi douter du Bordeaux-Toulouse = 7,00h à 50km/h !!

Ainsi que du Bordeaux-La Rochelle à 160km/h et Nancy-Troyes à 170km/h et enfin Lyon-Troyes à 200km/h (il ne faut pas avoir peur des radars) !!

Il faudrait corriger ces quelques détails.

[vinci.novice]

Je suis un peux en retard sur ce poste, juste je crois que l'utilisation d'une matrice serais beaucoup plus simple pour avoir toute les informations concernant le graphe.
Exemple

Sommets
A
B
C
D
Arcs
A B 2
A C 4
C D 5
A D 6

--A B C D
A 0 2 4 0
B 0 0 0 0
C 0 0 0 5
D 0 0 0 6

J'ai déjà réalisé ce projet comme travail scolaire en graphique, voici le code :

Dikstra.java

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
171
172
173
174
175
176
177
178
179
180
181
package is.RechercheOperationel;
 
import java.awt.Frame;
import java.awt.GridLayout;
import java.awt.List;
import java.awt.event.WindowEvent;
import java.awt.event.WindowListener;
 
public class Dikstra 
{
 
	double matrice[][]= 
	{		{0,6,1.0/0,2,1.0/0,1.0/0,8,1.0/0}, 
			{1.0/0,0,1.0/0,1,1.0/0,1.0/0,2,1.0/0}, 
			{1.0/0,4,0,1.0/0,1.0/0,1,1.0/0,1.0/0},
			{1.0/0,1.0/0,1.0/0,0,1,1.0/0,1.0/0,1.0/0},
			{1.0/0,2,8,1.0/0,0,9,1.0/0,1.0/0},
			{1.0/0,1.0/0,1.0/0,1.0/0,1.0/0,0,1.0/0,2},
			{1.0/0,1.0/0,3,1.0/0,1.0/0,1.0/0,0,7},
			{1.0/0,1.0/0,1.0/0,1.0/0,1.0/0,1.0/0,1.0/0,0},
	};
	boolean d[]={false,false,false,false,false,false,false,false};
	double t[]={0,6,1.0/0,2,1.0/0,1.0/0,8,1.0/0};
	List liste=new List();
	Frame fenetre=new Frame();
	public Dikstra()
	{
		appliquerAlgo();
	}
	public Dikstra(double matrice[][])
	{
		fenetre.add(liste);
		fenetre.setLayout(new GridLayout());
		fenetre.setVisible(true);
		fenetre.setBounds(200,200,600,600);
		fenetre.addWindowListener(new WindowListener(){
 
			@Override
			public void windowActivated(WindowEvent e) {
				// TODO Auto-generated method stub
 
			}
 
			@Override
			public void windowClosed(WindowEvent e) {
				// TODO Auto-generated method stub
 
			}
 
			@Override
			public void windowClosing(WindowEvent e) {
				// TODO Auto-generated method stub
				fenetre.setVisible(false);
				liste.removeAll();
 
			}
 
			@Override
			public void windowDeactivated(WindowEvent e) {
				// TODO Auto-generated method stub
 
			}
 
			@Override
			public void windowDeiconified(WindowEvent e) {
				// TODO Auto-generated method stub
 
			}
 
			@Override
			public void windowIconified(WindowEvent e) {
				// TODO Auto-generated method stub
 
			}
 
			@Override
			public void windowOpened(WindowEvent e) {
				// TODO Auto-generated method stub
 
			}
 
		});
 
		this.matrice=matrice.clone();
		this.t=matrice[0].clone();
		appliquerAlgo();
	}
	public void appliquerAlgo()
	{
		int nb=matrice.length;
		while(--nb>0)
		{
			int a=posMin();
			if(a==-1)
			{
				System.out.println("Tout est dans D");
			}else
			{
				modSuc(a);
			}
			afficherAc();
		}
 
	}
	private void modSuc(int a)
	{
		for(int i=0;i<matrice[a].length;i++)
		{
			if(matrice[a][i]!=1.0/0)
			{
				if(t[i] > (t[a]+matrice[a][i]))
				{
					t[i]=t[a]+matrice[a][i];
				}
			}
		}
	}
	private void afficherAc()
	{
		StringBuffer sb=new StringBuffer();
 
		System.out.print("D = { ");
		sb.append("D = { ");
		for(int i=0;i<d.length;i++)
		{
			if(d[i])
			{
				System.out.print(" X"+(i+1)+" , ");
				sb.append(" X"+(i+1)+" , ");
			}
		}
		System.out.println(" }");
		sb.append(" }");
		liste.add(sb.toString());
		sb.setLength(0);
 
		for(int i=0;i<t.length;i++)
		{
			System.out.print(t[i]+" | ");
			sb.append(t[i]+" | ");
		}
		liste.add(sb.toString());
		liste.add("");
		System.out.println();
		System.out.println();
 
	}
	private int posMin()
	{
		double a=1.0/0;
		int b=-1;
		for(int i=0;i<t.length;i++)
		{
			if(t[i]<a && !d[i])
			{
				a=t[i];
				b=i;
			}
		}
		d[b]=true;
		return b;
	}
	public void afficher()
	{
		for(int i=0;i<matrice.length;i++)
		{
			for(int j=0;j<matrice[i].length;j++)
			{
				System.out.print(matrice[i][j]+" ");
			}
			System.out.println();
		}
	}
 
 
	public static void main(String[] args) 
	{
		new Dikstra();
	}
 
}

Graphique.java

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
package is.RechercheOperationel;
 
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.WindowEvent;
import java.awt.event.WindowListener;
import java.util.Scanner;
 
public class Graphique extends Frame implements WindowListener{
 
 
	TextField texte[][];
	Button lancer=new Button("Lancer L'algo");
	MenuBar mb=new MenuBar();
	Menu m=new Menu("Algorithme");
	MenuItem mi=new MenuItem("Dikstra");
	int n;
 
 
	public Graphique(int n)
	{
		this.n=n;
		this.setLayout(new GridLayout(n,n));
		this.addWindowListener(this);
		this.setBounds(200,200,600,600);
		mb.add(m);
		m.add(mi);
		this.setMenuBar(mb);
		mi.addActionListener(new ActionListener()
		{
			public void actionPerformed(ActionEvent e) 
			{
				new Dikstra(retMatrice());
			}
 
		});
		texte=new TextField[n][n];
		for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			texte[i][j]=new TextField();
			this.add(texte[i][j]);
		}
		this.setVisible(true);
	}
 
 
	public double[][] retMatrice()
	{
		double[][] matrice=new double[n][n];
 
		for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			if(texte[i][j].getText().equals("inf"))
			{
				matrice[i][j]=1.0/0;
			}else
			{
				matrice[i][j]=Double.parseDouble(texte[i][j].getText());
			}
		}
 
		return matrice;
	}
	public static void main(String[] args) 
	{
 
		Scanner s=new Scanner(System.in);
		System.out.print("Donnez la taille du coté de la matrice : ");
		new Graphique(s.nextInt());
 
	}
 
 
 
	@Override
	public void windowActivated(WindowEvent e) {
		// TODO Auto-generated method stub
 
	}
 
 
 
	@Override
	public void windowClosed(WindowEvent e) {
		// TODO Auto-generated method stub
 
	}
 
 
 
	@Override
	public void windowClosing(WindowEvent e) {
		System.exit(0);
 
	}
 
 
 
	@Override
	public void windowDeactivated(WindowEvent e) {
		// TODO Auto-generated method stub
 
	}
 
 
 
	@Override
	public void windowDeiconified(WindowEvent e) {
		// TODO Auto-generated method stub
 
	}
 
 
 
	@Override
	public void windowIconified(WindowEvent e) {
		// TODO Auto-generated method stub
 
	}
 
 
 
	@Override
	public void windowOpened(WindowEvent e) {
		// TODO Auto-generated method stub
 
	}
 
}