A voir également:
- Dijkstra’s algorithm
- Algorithm facebook - Guide
3 réponses
mon EMAIL EN CAS DE PROBLEME : sami_oubbati@yahoo.com
voici le programme et il est simple a comprendre:
program graphe(value);
uses crt;
type matrice=array[1..10,1..10] of integer;
tableau=array[1..10]of integer;
var i,j,k,n,v,m,min_tab,p,x,y,l,Som_dep:integer;
tab,lamda:tableau;
C,D,cout:matrice;
stop,trouve :boolean;
{Calcul le minimum de 2 entiers}
{programme}
begin
clrscr;
write('entrer le nombre des sommets');
readln(n);
begin
for i:= 1 to n do
for j:=1 to n do
begin
if i<>j then
begin
Write('entrez(',i,',',j,') :=');readln(v);
c[i,j]:=v;
end
else
begin
writeln(' (',i,',',j,') :=0');c[i,j]:=0;
end;
end;
end;
writeln;writeln;writeln;
TextColor(14);
write(' Donner le Sommet de d‚part:x');
TextColor(12);
read(Som_dep); readln;
D[1,Som_dep]:=0;
for j:=1 to Som_dep-1 do
begin
D[1,j]:=100;
end;
for j:=Som_dep+1 to n do
begin
D[1,j]:=100;
end;
min_tab:=D[1,Som_dep];cout[Som_dep,Som_dep]:=min_tab;
p:=Som_dep;l:=1;lamda[1]:=Som_dep;
while l<n do
begin
x:=1;
for j:=1 to n do
begin
if (C[p,j]<>100)and(C[p,j]<>0) then
begin
tab[x]:=j;
x:=x+1;
end
else D[l+1,j]:=100;
end;
if x>1 then
begin
m:=x-1;
for j:=1 to n do
begin
stop:=false;x:=1;
while (x<=m) and (stop=false) do
begin
if j=tab[x] then
begin
y:=(min_tab+C[p,j]);
D[l+1,j]:=minimum(D[l,j],y);
trouve:=false;
i:=1;
while (trouve=false)and(i<l) do
begin
if (j=lamda[i])then
begin
D[l+1,j]:=100;
trouve:=true;
end
else i:=i+1;
end;
stop:=true;
end
else
begin
if (j<>p)and(j<>tab[x]) then D[l+1,j]:=D[l,j]
else if(j=p)and( j<>tab[x]) then D[l+1,j]:=100;
x:=x+1;
end;
end;
end;
end;
min_tab:=D[l+1,1];
for k:=2 to n do
begin
if D[l+1,k]<min_tab then
begin
min_tab:=D[l+1,k];
cout[Som_dep,k]:=D[l+1,k];
p:=k;
end;
end;
if min_tab=D[l+1,1] then
begin
p:=1;
cout[Som_dep,1]:=D[l+1,1];
end;
lamda[l+1]:=p;
l:=l+1;
end;
for i:=1 to n do
begin
j:=1;stop:=false;
while (stop=false)and(j<=n) do
begin
if lamda[j]=i then stop:=true
else j:=j+1;
end;
if stop=false then cout[som_dep,i]:=100;
end;
for k:=1 to n do
begin
writeln;TextColor(11);
writeln(' Le cout minimum de ',Som_dep,' vers le sommet',k,' =',cout[Som_dep,k]);
readln;
end;
end.
voici le programme et il est simple a comprendre:
program graphe(value);
uses crt;
type matrice=array[1..10,1..10] of integer;
tableau=array[1..10]of integer;
var i,j,k,n,v,m,min_tab,p,x,y,l,Som_dep:integer;
tab,lamda:tableau;
C,D,cout:matrice;
stop,trouve :boolean;
{Calcul le minimum de 2 entiers}
{programme}
begin
clrscr;
write('entrer le nombre des sommets');
readln(n);
begin
for i:= 1 to n do
for j:=1 to n do
begin
if i<>j then
begin
Write('entrez(',i,',',j,') :=');readln(v);
c[i,j]:=v;
end
else
begin
writeln(' (',i,',',j,') :=0');c[i,j]:=0;
end;
end;
end;
writeln;writeln;writeln;
TextColor(14);
write(' Donner le Sommet de d‚part:x');
TextColor(12);
read(Som_dep); readln;
D[1,Som_dep]:=0;
for j:=1 to Som_dep-1 do
begin
D[1,j]:=100;
end;
for j:=Som_dep+1 to n do
begin
D[1,j]:=100;
end;
min_tab:=D[1,Som_dep];cout[Som_dep,Som_dep]:=min_tab;
p:=Som_dep;l:=1;lamda[1]:=Som_dep;
while l<n do
begin
x:=1;
for j:=1 to n do
begin
if (C[p,j]<>100)and(C[p,j]<>0) then
begin
tab[x]:=j;
x:=x+1;
end
else D[l+1,j]:=100;
end;
if x>1 then
begin
m:=x-1;
for j:=1 to n do
begin
stop:=false;x:=1;
while (x<=m) and (stop=false) do
begin
if j=tab[x] then
begin
y:=(min_tab+C[p,j]);
D[l+1,j]:=minimum(D[l,j],y);
trouve:=false;
i:=1;
while (trouve=false)and(i<l) do
begin
if (j=lamda[i])then
begin
D[l+1,j]:=100;
trouve:=true;
end
else i:=i+1;
end;
stop:=true;
end
else
begin
if (j<>p)and(j<>tab[x]) then D[l+1,j]:=D[l,j]
else if(j=p)and( j<>tab[x]) then D[l+1,j]:=100;
x:=x+1;
end;
end;
end;
end;
min_tab:=D[l+1,1];
for k:=2 to n do
begin
if D[l+1,k]<min_tab then
begin
min_tab:=D[l+1,k];
cout[Som_dep,k]:=D[l+1,k];
p:=k;
end;
end;
if min_tab=D[l+1,1] then
begin
p:=1;
cout[Som_dep,1]:=D[l+1,1];
end;
lamda[l+1]:=p;
l:=l+1;
end;
for i:=1 to n do
begin
j:=1;stop:=false;
while (stop=false)and(j<=n) do
begin
if lamda[j]=i then stop:=true
else j:=j+1;
end;
if stop=false then cout[som_dep,i]:=100;
end;
for k:=1 to n do
begin
writeln;TextColor(11);
writeln(' Le cout minimum de ',Som_dep,' vers le sommet',k,' =',cout[Som_dep,k]);
readln;
end;
end.
dcanl
Messages postés
2999
Date d'inscription
mercredi 7 septembre 2005
Statut
Contributeur
Dernière intervention
3 juin 2013
470
3 avril 2008 à 02:31
3 avril 2008 à 02:31
Salut.
T'as vu ça ? https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
@+
T'as vu ça ? https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
@+
10 nov. 2008 à 18:26