daily pastebin goal
2%
SHARE
TWEET

Untitled

a guest May 16th, 2018 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include <iostream>
  3. #include <conio.h>
  4. #include <windows.h>
  5. #include <iomanip>
  6. using namespace std;
  7. char NEWT[256];
  8. int v;
  9. HANDLE out = GetStdHandle(STD_OUTPUT_HANDLE);
  10. int main()
  11. {
  12.     srand(time(0));
  13.     setlocale(0, "Russian");
  14.     int i, j;
  15.     int infinity = 100;// Бесконечность
  16.     int VES[100][100];// Матрица весов графа
  17.  
  18.     int x[100];
  19.     // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
  20.     // x[i]=1 - кратчайший путь в i-ю вершину уже найден
  21.  
  22.     int DlinaPuti[100];//t[i] - длина кратчайшего пути от вершины s в i
  23.  
  24.     int PredVertex[100];//h[i] - вершина, предшествующая i-й вершине
  25.                         //на кратчайшем пути
  26.     int VERTEX = 10;
  27.     int p;
  28.     p = VERTEX;//Число вершин в графе
  29.     for (int i = 0; i < VERTEX; i++)
  30.     {
  31.         VES[i][i] = 0;
  32.         for (int j = i + 1; j < VERTEX; j++) {
  33.             VES[i][j] = rand() % 100;
  34.             VES[j][i] = VES[i][j];
  35.         }
  36.     }
  37.  
  38.     /*Вывод матрицы*/
  39.     //VES[3][0] = infinity;
  40.     //VES[4][0] = infinity;
  41.  
  42.     cout << setw(20) << "Матрица расстояний:";
  43.     cout << "" << endl;
  44.     cout << endl;
  45.     cout << "   |  1|  2|  3|  4|  5|  6|  7|  8|  9| 10|" << endl;
  46.     cout << setw(20) << "--------------------------------------------" << endl;
  47.     for (int i = 0; i<VERTEX; i++)
  48.     {
  49.         cout << setw(1) << "";
  50.         cout << setw(2) << i + 1 << "|";
  51.         for (int j = 0; j < VERTEX; j++)
  52.         {
  53.  
  54.             cout << setw(3) << VES[i][j];
  55.             cout << setw(1) << "|";
  56.  
  57.         }
  58.         cout << endl;
  59.         cout << setw(20) << "--------------------------------------------" << endl;
  60.     }
  61.     //VES[3][0] = infinity;
  62.     //VES[4][0] = infinity;
  63.  
  64.  
  65.     //
  66.     // Будем искать путь из вершины s в вершину g по циклу
  67.     int start;// Номер исходной вершины
  68.     int end;// Номер конечной вершины
  69.     cout << endl;
  70. N: cout << "Начальная вершина: "; // Номер может изменяться от 0 до p-1
  71.     cin >> start;
  72.     cout << endl;
  73.     if (start>(p - 1) && start<0)
  74.     {
  75.         cout << "Нет такой вершины повторите ввод..." << endl; goto N; // на случай неверных данных
  76.     }
  77.     start = start - 1;//так как массив начинается с 0 отнимаем от вводимой цифры 1
  78.     for (int prosto = 0; prosto<VERTEX; prosto++)
  79.     {
  80.         end = prosto;//цикл прогоняет алгоритм Флойда p-ое количество раз преврашая его в алгоритм Дейкстры  
  81.         if (end == start) continue;//исключаем просчет растояния между одной и той же точкой
  82.         else
  83.         {
  84.             // Инициализируем начальные значения массивов
  85.             int u;                                // Счетчик вершин
  86.             for (u = 0; u<p; u++)
  87.             {
  88.                 DlinaPuti[u] = infinity;                    //Сначала все кратчайшие пути из s в i
  89.                                                             //равны бесконечности
  90.                 x[u] = 0;                            // и нет кратчайшего пути ни для одной вершины
  91.             }
  92.             PredVertex[start] = 0;                     // s - начало пути, поэтому этой вершине ничего не предшествует
  93.             DlinaPuti[start] = 0;                      // Кратчайший путь из s в s равен 0
  94.             x[start] = 1;                              // Для вершины s найден кратчайший путь
  95.             v = start;                                 // Делаем s текущей вершиной
  96.  
  97.             while (1)
  98.             {
  99.                 // Перебираем все вершины, смежные v, и ищем для них кратчайший путь
  100.                 for (u = 0; u<p; u++)
  101.                 {
  102.                     if (VES[v][u] == 0)continue;      // Вершины u и v несмежные
  103.                     if (x[u] == 0 && DlinaPuti[u]>DlinaPuti[v] + VES[v][u]) //Если для вершины 'u' еще не
  104.                                                                             //найден кратчайший путь
  105.                                                                             // и новый путь в 'u' короче чем
  106.                                                                             //старый, то
  107.                     {
  108.                         DlinaPuti[u] = DlinaPuti[v] + VES[v][u];            //запоминаем более короткую длину пути в
  109.                                                                             //массив t[и]
  110.                         PredVertex[u] = v;                     //запоминаем, что v->u часть кратчайшего
  111.                                                                //пути из s->u
  112.                     }
  113.                 }
  114.  
  115.                 // Ищем из всех длин некратчайших путей самый короткий
  116.                 int w = infinity;                   // Для поиска самого короткого пути
  117.                 v = -1;                             // В конце поиска v - вершина, в которую будет
  118.                                                     // найден новый кратчайший путь. Она станет
  119.                                                     // текущей вершиной
  120.                 for (u = 0; u<p; u++)                  // Перебираем все вершины.
  121.                 {
  122.                     if (x[u] == 0 && DlinaPuti[u]<w)           // Если для вершины не найден кратчайший
  123.                                                                // путь и если длина пути в вершину 'u' меньше
  124.                                                                // уже найденной, то
  125.                     {
  126.                         v = u;                         // текущей вершиной становится 'u'-я вершина
  127.                         w = DlinaPuti[u];
  128.                     }
  129.                 }
  130.                 if (v == -1)
  131.                 {
  132.                     cout << "Нет пути из вершины " << start + 1; cout << " в вершину " << end + 1 << "." << endl;
  133.                     break;
  134.                 }
  135.                 if (v == end)                            // Найден кратчайший путь,
  136.                 {                                 // выводим его
  137.                     cout << "Кратчайший путь из вершины";
  138.                     cout << " "<< start + 1;
  139.                     cout << " в вершину ";
  140.                     cout << end + 1;
  141.                     cout << ":";
  142.                     u = end;
  143.                     while (u != start)
  144.                     {
  145.                         cout << " " << u + 1;
  146.                         u = PredVertex[u];
  147.                     }
  148.                     cout << " " << start + 1 << ". ";
  149.                     cout << "Длина пути - ";
  150.                     cout << DlinaPuti[end];
  151.                     cout << endl;
  152.                     break;
  153.                 }
  154.                 x[v] = 1;
  155.             }
  156.         }   cout << endl;
  157.  
  158.     }
  159.     cout << endl;
  160.     system("pause");
  161.     return 0;
  162. }
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