Поиск всех кратчайших путей методом Шимбелла

c++
  1. typedef struct {
  2.     int n, last;
  3. } Cell;
  4.  
  5. void findPathsShimbel(Cell **M, int n) {
  6.     int run = 1, min, i, j, k, sum;
  7.     while (run) {
  8.         run = 0;
  9.         for (i = 0; i < n; i++) {
  10.             for (j = 0; j < n; j++) {
  11.                 min = INT_MAX;
  12.                 for (k = 0; k < n; k++) {
  13.                     if (M[i][k].last == INT_MAX || M[k][j].last == INT_MAX)
  14.                         sum = INT_MAX;
  15.                     else sum = M[i][k].last + M[k][j].last;
  16.                     min = min > sum ? sum : min;
  17.                 }
  18.                 if (min < M[i][j].last) {
  19.                     run = 1;
  20.                     M[i][j].n = min;
  21.                 } else M[i][j].n = M[i][j].last;
  22.             }
  23.         }
  24.         for (i = 0; i < n; i++) {
  25.             for (j = 0; j < n; j++) {
  26.                 M[i][j].last = M[i][j].n;
  27.             }
  28.         }
  29.     }
  30. }
Поиск всех кратчайших путей в графе. На вход подается матрица смежности графа (поле last структуры), где на месте отсутствия связей должен быть INT_MAX, а по диагонали нули. Метод преобразует так матрицу, что наименьший путь с вершины i в вершину j будет равен M[i][j].last
Пример:
  1. for (i = 0; i < size; i++) {
  2.         for (j = 0; j < size; j++) {
  3.             fscanf(file, "%d", &M[i][j].last);// чтение веса дуги (i,j) из файла
  4.             if (M[i][j].last == -1) M[i][j].last = INT_MAX;// если в файле -1, то нет такой дуги
  5.             if (i == j) M[i][j].last = 0;// диагональные элементы =0
  6.         }
  7.     }
  8.     findPathsShimbel(M, size);// считаем
Назад

Реклама

Мы в соцсетях

tw tg yt gt