Five_NT

[C++]Algoritmul lui Dijkstra

Feb 24th, 2014
223
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. #include<iostream.h>
  2. #include<fstream.h>
  3.  
  4. const int maxi = 500;
  5. int i, j, a[100][100], arc, c, r, q, poz, x, y, s[100], t[100], d[100], mini, n;
  6.     ifstream f("date.in");
  7. void citire()
  8. {
  9.  
  10.     f>>n;
  11.     for(int i=1; i<=n; i++)
  12.     {
  13.         for(int j=1; j<=n; j++)
  14.             a[i][j] = maxi;
  15.         a[i][i] = 0;
  16.     }
  17.     f>>arc;
  18.     for(int i=1; i<=arc; i++)
  19.     {
  20.         f>>x>>y>>c;
  21.         a[x][y] = c;
  22.     }
  23.    
  24. }
  25.  
  26. void drum(int i)
  27. {
  28.     if(t[i])
  29.         drum(t[i]);
  30.     cout<<i<<" ";
  31. }
  32.  
  33. int main()
  34. {
  35.     citire();
  36.     cout<<"Punct de plecare: "; cin>>r;
  37.     cout<<"Punct de sosire: "; cin>>q;
  38.     cout<<'\n';
  39.     s[r] = 1;
  40.     for(int i=1; i<=n; i++)
  41.     {
  42.         d[i] = a[r][i];
  43.         if(i != r) if(d[i] < maxi) t[i] = r;
  44.     }
  45.     for(int i=1; i<=n-1; i++)
  46.     {
  47.         mini=maxi;
  48.         for(int j=1; j<=n; j++)
  49.             if(s[j] == 0)
  50.                 if(d[j] < mini)
  51.                 {
  52.                     mini = d[j];
  53.                     poz = j;
  54.                 }
  55.         s[poz] = 1;
  56.         for(int j=1; j<=n; j++)
  57.             if(s[j] == 0)
  58.                 if(d[j] > d[poz] + a[poz][j])
  59.                 {
  60.                     d[j] = d[poz] + a[poz][j];
  61.                     t[j] = poz;
  62.                 }
  63.     }      
  64.     if(r < q)
  65.     {
  66.         for(int i=r; i<=q; i++)
  67.             if(i != r)
  68.                 if(t[i])
  69.                     if(i == q)
  70.                     {
  71.                         cout<<"Drumul de la "<<r<<" la "<<i<<" este "<<d[i]<<" si trece prin varf:";
  72.                         drum(i);
  73.                         cout<<'\n';
  74.                     }
  75.                     else cout<<"Nu avem drum de la "<<r<<" la "<<i<<'\n';
  76.     }
  77.     else
  78.     {
  79.         for(int i=r; i>=q; i--)
  80.             if(i != r)
  81.                 if(t[i])
  82.                     if(i == q)
  83.                     {
  84.                         cout<<"Drumul de la "<<r<<" la "<<i<<" este "<<d[i]<<" si trece prin varf.";
  85.                         drum(i);
  86.                         cout<<'\n';
  87.                     }
  88.                     else cout<<"Nu avem drum de la "<<r<<" la "<<i<<'\n';
  89.     }  
  90.     f.close();
  91.     return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment