r1411

Флойд с выводом пути

Jun 13th, 2021
690
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. int p[100][100];    // Матрица добавленных вершин
  7.  
  8. // Вывести путь от i до j
  9. void printPath(int i, int j) {
  10.     int k = p[i][j];
  11.     if (k != 0) {
  12.         printPath(i, k);
  13.         cout << k << " ";
  14.         printPath(k, j);
  15.     }
  16. }
  17.  
  18. void main() {
  19.     setlocale(LC_ALL, "Russian");
  20.  
  21.     int n;
  22.     cout << "Введите колво вершин" << endl;
  23.     cin >> n;
  24.  
  25.     for (int i = 1; i <= n; i++)
  26.         for(int j = 1; j <= n; j++)
  27.             c[i][j] = 10000;
  28.    
  29.     cout << "Вводите смежные вершины (формат: <v1> <v2> <стоимость>, окончание ввода - 0 0 0)" << endl;
  30.     int v1, v2, cost;
  31.     cin >> v1 >> v2 >> cost;
  32.     while (v1 != 0 && v2 != 0) {
  33.         c[v1][v2] = cost;
  34.         c[v2][v1] = cost; // Убрать, если граф ориентированый.
  35.         cin >> v1 >> v2 >> cost;
  36.     }
  37.  
  38.     for (int i = 1; i <= n; i++) {
  39.         for (int j = 1; j <= n; j++) {
  40.             if (i == j)
  41.                 a[i][j] = 0;
  42.             else
  43.                 a[i][j] = c[i][j];
  44.  
  45.             p[i][j] = 0;
  46.         }
  47.     }
  48.  
  49.     //Конец инициализации, начало самого алгоритма
  50.  
  51.     for (int k = 1; k <= n; k++)
  52.         for (int i = 1; i <= n; i++)
  53.             for (int j = 1; j <= n; j++)
  54.                 if (a[i][k] + a[k][j] < a[i][j]) {
  55.                     a[i][j] = a[i][k] + a[k][j];
  56.                     p[i][j] = k;
  57.                 }
  58.  
  59.     for (int i = 1; i <= n; i++) {
  60.         for (int j = i + 1; j <= n; j++) {
  61.             cout << "Стоимость пути " << i << " -> " << j << ": " << a[i][j] << endl;
  62.             cout << "Сам путь: ";
  63.  
  64.             cout << i << " ";
  65.             printPath(i, j);
  66.             cout << j << endl;
  67.         }
  68.     }
  69. }
  70.  
RAW Paste Data