SHARE
TWEET

Untitled

a guest Jan 22nd, 2020 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4. double **A;
  5. int n;
  6. int *predecesor;
  7. const double MaxInf = 1.e20;
  8. void Citire_Date(const char numeFisier[]) {
  9.     int i,j;
  10.     double c;
  11.     ifstream fin(numeFisier);
  12.     fin >> n;
  13.     A = new double*[n];
  14.     if(A==0) {
  15.         cout<<"alocare esuata";
  16.         exit(1);
  17.     }
  18.     for(i=0;i<n;i++) {
  19.         A[i]=new(nothrow) double[n];
  20.         if(A[i]==0){
  21.             cout<<"alocare esuata";
  22.             exit(1);
  23.         }
  24.         for(j=0;j<n;j++)
  25.             if(i==j)
  26.                 A[i][j]=0.0;
  27.             else
  28.                 A[i][j] = MaxInf;
  29.      }
  30.     while(fin>>i>>j>>c)
  31.         A[i][j]=c;
  32.     fin.close();
  33. }
  34. void afisare(int i) {
  35.     if (predecesor[i] !=  -1)
  36.         afisare(predecesor[i]);
  37.     cout  << i << " ";
  38. }
  39. int main() {
  40.     Citire_Date("in.txt");
  41.     predecesor = new int [n];
  42.     int *selectat = new int[n];
  43.     double *dmin = new double[n], min;
  44.     int v, w = -1;
  45.     for (int i = 0; i < n; i++) {
  46.         selectat[i] = 0;
  47.         dmin[i] = 0.0;
  48.         predecesor[i] = -1;
  49.     }
  50.     cout << "v: ";
  51.     cin >> v;
  52.     selectat[v] = 1;
  53.     for (int i = 0; i < n; i++) {
  54.         dmin[i] = A[v][i];
  55.         if (i != v)
  56.             if (dmin[i] < MaxInf) predecesor[i] = v;
  57.     }
  58.     for (int i = 1; i <= n - 1; i++){
  59.         min = MaxInf;
  60.         for (int j = 0; j < n; j++)
  61.             if (selectat[j] == 0)
  62.                 if (dmin[j] < min) {
  63.                     min = dmin[j];
  64.                     w = j;
  65.                 }
  66.         if (w != -1) {
  67.             selectat[w] = 1;
  68.             for (int j = 0; j < n; j++)
  69.                 if (selectat[j] == 0)
  70.                     if (dmin[j] > dmin[w] + A[w][j]) {
  71.                         dmin[j] = dmin[w] + A[w][j];
  72.                         predecesor[j] = w;
  73.                     }
  74.         }
  75.     }
  76.     for (int i = 0; i < n; i++)
  77.         if (i != v)
  78.             if (predecesor[i] != -1) {
  79.                 cout << "Costul  drumului  de la " << v << " la " << i
  80.                      << " este " << dmin[i] << endl;
  81.                 afisare(i);
  82.                 cout << endl;
  83.             } else
  84.                 cout  << "Nu  exista  drum de la " << v << " la " << i << endl;
  85.     return 0;
  86. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top