Implémentation de l'algorithme de Dijkstra

Version imprimable

23/04/2009, 23h45
sparklegi

Exercice sur les graphes
bonsoir,
je suis un nouveau inscrit sur developpez.net/.
j'ai un TP a faire au pascal .
Voici le tp :
Citation:
soit un graph représentant les différentes villes d'un pays .
Ecrire un programme qui gére les differentes voyages en répondant aux questions du genre :
L'existence d'un chemin entre 2 villes .
la distance a parcourir entre 2 villes .
tous les chemins entre 2 villes en précisant les differentes distances .
le chemin le plus court entre 2 villes .
s'il vous plait aidez moi ...a faire ce tp .
et merci d'avance.
24/04/2009, 00h42
krachik

Bonjour et bienvenue

Peut-on savoir comment on peut t'aider a faire ce TP?
Vu que tu as un énnoncé, lances toi. et dis nous ce qui te bloques ou la où tu coinces, ou ce que tu as déjà fait et qui ne marche pas. Je suppose que tu as eu de cours sur quelques algorithmes sur les graphes.

Cordialement
24/04/2009, 01h09
dot-_-net

Commence a poster ton code et on t’aidera
24/04/2009, 12h16
sparklegi

merci .
mon problem que je connais r1 sur les graphes .
donner moi une idée cmnt faire .
et es'qu il faut utiliser des matrices ????? .
24/04/2009, 13h49
darrylsite

Je trouve un peu bizzard qu'on te donne un tp sur les graphes sachant que tu ne connais rien sur les graphes.
Sinon les questions sont plutot classiques et on peut les resoudre avec les algorithmes suivants :
..Recherche en profondeur d'abord
..Algorithme de Dijsktra
...
24/04/2009, 13h51
droggo

Nao,

Citation:

Envoyé par sparklegi

merci .
mon problem que je connais r1 sur les graphes .
donner moi une idée cmnt faire .
et es'qu il faut utiliser des matrices ????? .

Allons, soyons sérieux.

C'est typiquement le genre d'exercice qu'aucun prof ne pose sans qu'il y ait eu les cours nécessaires.
24/04/2009, 13h57
sparklegi

merci .
si vous avez un tutoriel sur les graphes en pascal .
svp donner le moi .

merci beaucoup de votre reponce.

bonsoir voici mon code .
mais je me suis bloquer .

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
program tp;
uses crt;
var t:array[0..5,0..5] of string;
    t2:array[0..5,0..5] of integer;
 i,j,k:integer;
 
 
 
begin
clrscr;
(* l'existance d'un chemin entre deux villes*)
t2[0,1]:=23;
t2[0,2]:=25;
t2[0,3]:=19;
t2[0,4]:=18;
t2[0,5]:=12;
 
t2[1,0]:=23;
t2[2,0]:=25;
t2[3,0]:=19;
t2[4,0]:=18;
t2[5,0]:=12;
for i:=1 to 5 do
begin
for j:=1 to 5 do
if i=j then t2[i,j]:=0
else t2[i,j]:=1;
end;
(* fin de l'existance d'un chemin entre 2 villes *)
 
(* remplir le deusime matrice avec les distances entres les villes *)
t[0,0]:='           ';
t[0,1]:='annaba     ';
t[0,2]:='constantine';
t[0,3]:='setif      ';
t[0,4]:='jijel      ';
t[0,5]:='tebessa    ';
 
t[1,0]:='annaba     ';
t[2,0]:='constantine';
t[3,0]:='setif      ';
t[4,0]:='jijel      ';
t[5,0]:='tebessa    ';
for i:=1 to 5 do
begin
for j:=1 to 5 do
if i=j then t[i,j]:='0          ';
end;
t[2,1]:='156        ';
t[3,1]:='287        ';
t[4,1]:='255        ';
t[5,1]:='227        ';
 
t[1,2]:='156        ';
t[3,2]:='131        ';
t[4,2]:='146        ';
t[5,2]:='198        ';
 
t[1,3]:='287        ';
t[2,3]:='131        ';
t[4,3]:='146        ';
t[5,3]:='329        ';
 
t[1,4]:='255        ';
t[2,4]:='146        ';
t[3,4]:='137        ';
t[5,4]:='344        ';
 
t[1,5]:='227        ';
t[2,5]:='198        ';
t[3,5]:='329        ';
t[4,5]:='344        ';
for i:=0 to 5 do
begin
  for j:=0 to 5 do
  write(t[i,j],' ');
writeln;
end;
(* fin de remplir la deusime matrice avec les distances entres deux villes *)
 
readkey;
end.

08/05/2009, 11h38
sparklegi

hey les amis aidez moi ...
svp je veut savoir une méthode pour remplir une matrice symétrique a deux dimensions ...
j'ai poster mon code source ...et personne m'a adiez .