Explicarea algoritmului



Programul in C++
#include<fstream.h>
int a[20][20], n, m, k=1;
int viz[20], d[20], tata[20];
const infinit = 10000;
 
void citiregraf()
{
  int i,x, y, j, c;
  ifstream f ("graf.in");
  f>>n>>m;
  for(i=1; i<=m; i++)
   { f>>x>>y>>c;
    a[x][y]=a[y][x]=c;
   }
  for (i=1; i<=n; i++)
    for(j=1; j<=n; j++)
      if(a[i][j]==0) a[i][j]=infinit;
  f.close();
}
 
void drum(int i)
{
  if(tata[i]!=0)
    {
      drum(tata[i]);
      cout<<","<<i;
    }
  else cout<<i;
}
 
void alg_dijkstra()
 {
   int pas, min, k, i;
   for(pas=1; pas<=n-1; pas++)
     {
       min=infinit;
       for(i=1; i<=n; i++)
         if((viz[i]==0) && (d[i]<min))
           { min=d[i]; k=i; }
       viz[k]=1;
       for(i=1; i<=n; i++)
         if((viz[i]==0) && (d[k]+a[k][i]<d[i]))
           { d[i]=d[k]+a[k][i]; tata[i]=k; }
     }
 }
 
void main()
{ int i, s;
  citiregraf();
  cout<<"dati nodul de start"; cin>>s;
 
  for(i=1; i<=n; i++)
    {
      viz[i]=0;
      d[i]=a[s][i];
      if(d[i]<infinit)
    tata[i]=s;
      else tata[i]=0;
    }
  viz[s]=1; tata[s]=0; d[s]=0;
  alg_dijkstra();
 
  for(i=1; i<=n; i++)
    {
      cout<<"drumul minim de la "<<s<<" la "<<i<<" este: ";
      drum(i);
      cout<<endl<<"costul este: "<<d[i]<<endl;
    }
 
}