r1411

Центр графа Флойдом

Jun 13th, 2021
972
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int a[100][100];    // Матрица смежности
  5. int c[100][100];    // Матрица стоимостей
  6.  
  7. void main() {
  8.     setlocale(LC_ALL, "Russian");
  9.  
  10.     int n;
  11.     cout << "Введите колво вершин" << endl;
  12.     cin >> n;
  13.  
  14.     for (int i = 1; i <= n; i++)
  15.         for (int j = 1; j <= n; j++)
  16.             c[i][j] = 10000;
  17.  
  18.     cout << "Вводите смежные вершины (формат: <v1> <v2> <стоимость>, окончание ввода - 0 0 0)" << endl;
  19.     int v1, v2, cost;
  20.     cin >> v1 >> v2 >> cost;
  21.     while (v1 != 0 && v2 != 0) {
  22.         c[v1][v2] = cost;
  23.         c[v2][v1] = cost; // Убрать, если граф ориентированый.
  24.         cin >> v1 >> v2 >> cost;
  25.     }
  26.  
  27.     for (int i = 1; i <= n; i++)
  28.         for (int j = 1; j <= n; j++)
  29.             if (i == j)
  30.                 a[i][j] = 0;
  31.             else
  32.                 a[i][j] = c[i][j];
  33.  
  34.     //Конец инициализации, начало самого алгоритма
  35.  
  36.     for (int k = 1; k <= n; k++)
  37.         for (int i = 1; i <= n; i++)
  38.             for (int j = 1; j <= n; j++)
  39.                 if (a[i][k] + a[k][j] < a[i][j])
  40.                     a[i][j] = a[i][k] + a[k][j];
  41.  
  42.     // Определение центра графа:
  43.  
  44.     int d[100] = { 0 };
  45.  
  46.     for (int j = 1; j <= n; j++) {
  47.         int max = 0;
  48.         for (int i = 1; i <= n; i++) {
  49.             if (a[i][j] > max)
  50.                 max = a[i][j];
  51.         }
  52.         d[j] = max;
  53.     }
  54.  
  55.     int min = 1000;
  56.     for (int i = 1; i <= n; i++)
  57.         if (d[i] < min)
  58.             min = d[i];
  59.  
  60.     cout << "Центр: ";
  61.     for (int i = 1; i <= n; i++)
  62.         if (d[i] == min)
  63.             cout << i << " ";
  64.     cout << endl;
  65.  
  66. }
RAW Paste Data