Facebook
From Matyo, 1 Week ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 158
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int N = 50;
  5. int c[N][N];       // ценовата матрица с разстоянията
  6. bool s[N] = { false };    // определя дали върха е посетен или не. Първоначално всички са непосетени
  7. int d[N];          // масив на най късите разстояния от началния до всеки един от останалите.
  8. int p[N];          //множество S реализирано като масив. Списъка с избраните върхове.
  9.  
  10. int convert(int a[], int n)
  11. {   // функцията намира върха до когото разстоянието от началния до него е най кратко и връща позицията му
  12.     // което отговаря на самия връх.
  13.     int min = a[0];
  14.     int pos = 0;
  15.     for (int i = 1; i < n; i++)
  16.     {
  17.         if (min == 0 && s[i]==0)
  18.         {
  19.             min = a[i];
  20.             pos = i;
  21.         }
  22.         if (a[i] < min && a[i]!=0 && s[i]==0)
  23.         {
  24.             min = a[i];
  25.             pos = i;
  26.         }
  27.     }
  28.     return pos;
  29.    
  30. }
  31. void dijkstra(int node, int n)
  32. {
  33.     int w, i;
  34.     s[node] = true;                // определяме първия началня връх за посетен
  35.     p[0] = node;                // добавя този връх в масива p.
  36.     for (i = 1; i < n; i++)
  37.     {   // смятаме разстоянията от началния връх до i-тия;
  38.         d[i] = c[node][i]; p[i] = 0;
  39.     }
  40.    
  41.     for (i=1; i<n; i++)
  42.     {
  43.         w = convert(d, n);
  44.        
  45.         // избиране на връх w, за който d[w] е min;
  46.         s[w] = true; //добавяне на w към маркиран
  47.         p[i] = w;   // и добавяме върхът като следващ избран
  48.         for (int j=1; j<n; j++)
  49.             if (s[j] == false)  //проверяваме дали текущия връх j е посетен
  50.                 if (c[w][j] != 0) //проверяваме дали има директен път от връх w до връх j.
  51.                 { // ако до този момент е липсвало разстоянието до j-тия връх от началния или то е по голямо от новото
  52.                   // пресметнато, то то се добавя като ново разстояние на мястото на старото.
  53.                     if (d[j] == 0)
  54.                         d[j] = (d[w] + c[w][j]);
  55.                     if (d[j] > (d[w] + c[w][j]))
  56.                         d[j] = d[w] + c[w][j];
  57.                 }
  58.     }
  59. }
  60.  
  61. int main()
  62. {
  63.     int n, vrah, start, end, nrebra, lw;
  64.     // n - broi varhove v grafa;
  65.     // vrah - na4alen vrah za prilagane na algorityma;
  66.     // start - na4alen vrah za dobavqshto rebro;
  67.     // end - kraen vrah za dobavqshto rebro;
  68.     // nrebra - broi na dobavqnite rebra;
  69.     // lw - stojnost na dobavqnoto rebro;
  70.    
  71.  
  72.     //----------upatvane za potrebitelq i predstavqne na neobhodimite danni ------------------------------
  73.     cout << "Vavedi broq na varhovete n=";
  74.     cin &gt;&gt; n;
  75.     cout &lt;&lt; "Predstavqneto na grafa se izvarsha 4rez matricata na rastoqniqta. Parviq vrah na grafa se priema s index 0" << endl;
  76.     for (int i = 0; i < n; i++)
  77.     {  
  78.         for (int j = 0; j < n; j++)
  79.             c[i][j] = 0;
  80.     }
  81.     cout << "Broq na rebrata v grafa sa: ";
  82.     cin >> nrebra;
  83.     cout << "Vavedi mejdu koi varhove na grafa iskash da dobavish rebro, kato izpolzvash indexite na incidentnite varhove"<<endl;
  84.     for (int i =0; i<nrebra; i++)
  85.     {
  86.         cout << "Na4alen vrah na novoto rebro e: ";
  87.         cin >> start;
  88.         cout << "Kraen vrah na novoto rebro e: ";
  89.         cin >> end;
  90.         cout << "Vavedi daljinata na tova rebro: ";
  91.         cin >> lw;
  92.         c[start][end]=lw;
  93.     }
  94.     cout << "Poso4i ot koi vrah da zapo4ne obhojdaneto: ";
  95.     cin >> vrah;
  96.     //------------------------------------------------------------------------------
  97.  
  98.  
  99.  
  100.  
  101.  
  102.     //--------------predstavqne na matricata na razstoqniqta-------------------------
  103.     cout << "Matricata C izglejda po sledniq na4in:";
  104.     cout << endl;
  105.     for (int i = 0; i < n; i++)
  106.     {
  107.         for (int j = 0; j < n; j++)
  108.             cout << " " << c[i][j];
  109.         cout << endl;
  110.     }
  111.     //---------------------------------------------------------------------------------
  112.  
  113.  
  114.  
  115.  
  116.     //----------------izvikvane na algoritam dijkstra-------------------------
  117.     dijkstra(vrah, n);
  118.     //-----------------------------------------------------------------------
  119.    
  120.    
  121.     cout << endl;
  122.    
  123.  
  124.  
  125.     //--------------rezultata ot izpalnenieto na algoritama-------------------------
  126.     cout << "Varhovete shte se ocvetqt v slednata posledovatelnost: ";
  127.     for (int i = 0; i < n; i++)
  128.         cout << " " << p[i];
  129.     cout << endl;
  130.     cout << "Naj kratkiq pat do vseki edin vrah e sledniq:          ";
  131.     cout << endl;
  132.     for (int i = 0; i < n; i++)
  133.         cout << p[i] << "->" << d[p[i]] << endl;;
  134.     //---------------------------------------------------------------------------
  135. }