На этом шаге мы рассмотрим вычисление путей в бесконтурных сетях.
Займемся теперь вторым случаем, для которого известен алгоритм нахождения расстояний от фиксированной вершины за время O(n2), а именно случаем, когда граф является бесконтурным (веса дуг могут быть произвольными).
При описании алгоритма нахождения путей в бесконтурном графе мы можем предположить, что каждая дуга идет из вершины с меньшим номером в вершину с большим номером.
Пример. Нахождение расстояний от источника до всех вершин в бесконтурном графе.
#include <iostream.h> #define MaxNodes 9 #define B 1000 //Машинный эквивалент бесконечности. class Spisok { private: int A[MaxNodes][MaxNodes]; //Матрица весов дуг. int D[MaxNodes]; //Матрица расстояний от источника до //всех вершин графа. public: void Vvod_Ves(); void Reshenie (); }; void main () { Spisok A; A.Vvod_Ves(); A.Reshenie(); } void Spisok::Reshenie () { int S; // Начальная вершина пути (источник). int i,j; S = 0; //Инициализация. for (j=1;j<MaxNodes;j++) D[j] = B; D[S] = 0; //Вычисление матрицы расстояний от источника до //всех вершин графа. for (j=1;j<MaxNodes;j++) for (i=0;i<MaxNodes;i++) if (A[i][j]!=0 && D[j]>D[i]+A[i][j]) D[j] = D[i]+A[i][j]; cout << "Матрица расстояний: \n"; for (i=0;i<MaxNodes;i++) cout << D[i] << " "; cout << endl; } void Spisok::Vvod_Ves() //Ввод матрицы весов дуг заданного графа. { cout << "Вводите элементы матрицы весов дуг по строкам:\n"; for (int i=0;i<MaxNodes;i++) for (int j=0;j<MaxNodes;j++) { cout << "Введите A[" << (i+1) << "," << (j+1) << "]: "; cin >> A[i][j]; if ( A[i][j]==0 ) A[i][j] = B; } }
Проверьте работу программы для следующей путевой матрицы:
0 1 0 2 0 0 1 0 0
0 0 2 0 7 0 0 0 0
0 0 0 0 0 10 0 0 5
0 0 0 0 5 0 0 0 0
0 0 0 0 0 6 0 1 0
0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 3 0
0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 0
При выполнении приложения будет получен следующий результат:
Матрица расстояний:
0 1 3 2 7 13 1 4 8
Приведенный алгоритм может найти применение в методах управления выполнением проекта, называемых PERT (Project Evaluation and Review Technique) или CPM (Critical Path Method). Эти методы основываются на построении графа (сети PERT или сети CPM), дуги которого соответствуют некоторым элементарным задачам, составляющим проект, а их веса указывают на время, необходимое для решения отдельных задач. Кроме этого, мы предполагаем, что для произвольных дуг этого графа (u,v) и (v,t) задача, изображаемая дугой (u,v), должна быть закончена перед началом решения задачи, изображаемой дугой (v,t). Легко заметить, что такой граф должен быть бесконтурным.
Нашей задачей является нахождение самого длинного пути из вершины s, соответствующей началу проекта, до вершины t, соответствующей его окончанию. Такой путь называется критическим. Его длина определяет время, необходимое для реализации всего проекта.
Эта задача сводится к задаче о кратчайшем пути путем изменения знака каждого веса A(u,v), где u->v, на обратный.
Так, например, выполните предыдущую программу для следующей путевой матрицы:
0 -1 0 -2 0 0 1 0 0
0 0 -2 0 -7 0 0 0 0
0 0 0 0 0-10 0 0 -5
0 0 0 0 -5 0 0 0 0
0 0 0 0 0 -6 0 -1 0
0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 -3 0
0 0 0 0 0 0 0 0 -5
0 0 0 0 0 0 0 0 0
Результат будет следующим:
Матрица расстояний:
0 -1 -3 -2 -8 -14 1 -9 -14
Пример [1, с.100-104].
//Планирование критического пути (анализ сети ПЕРТ) //Автор алгоритма: Leavenworth B. (CACM, 1961, 3). #include <iostream.h> void Critical_Path (int n, int i[], int j[], int dij[], int *s1, int *s2, int *f1, int *f2, int *tf, int *ff) { int k,index,max,min; int ti[20],te[20]; index = 0; for (k=0;k<n;k++) { if ( i[k]==index+1 ) index = i[k]; ti[k] = 0; te[k] = 9999; } for (k=0;k<n;k++) { max = ti[i[k]] + dij[k]; if ( ti[j[k]]<max ) ti[j[k]] = max; } te[j[n-1]] = ti[j[n-1]]; for (k=n-1;k>=0;k--) { min = te[j[k]] - dij[k]; if ( te[i[k]]>min ) te[i[k]] = min; } for (k=0;k<n;k++) { s1[k] = ti[i[k]]; f1[k] = s1[k] + dij[k]; f2[k] = te[j[k]]; s2[k] = f2[k] - dij[k]; tf[k] = f2[k] - f1[k]; ff[k] = ti[j[k]] - f1[k]; } } void main() { int n; // Общее количество работ по проекту // (количество ребер ориентированного графа). int i[20]; // Вектор-пара, представляющая k-ю работу, int j[20]; // которая понимается как стрелка, связыва- // ющая событие i[k] с событием j[k] // Граф задан массивом ребер: // (i[0],j[0]),(i[1],j[1]),...,(i[n-1],j[n-1]) // Должно быть выполнено: // i[0]=1, i[k]<i[k+1], i[k]<j[k]. int dij[20];// dij[k] - продолжительность k-й операции. int s1[20]; // s1[k] - самый ранний срок начала k-й операции. int s2[20]; // s2[k] - самый поздний срок начала k-й. int f1[20]; // f1[k] - самый ранний срок завершения k-й. int f2[20]; // f2[k] - самый поздний срок завершения k-й операции. int tf[20]; // tf[k] - полный резерв времени k-й операции. int ff[20]; // ff[k] - свободный резерв времени k-й операции. int k; // Параметр цикла. cout << "Введите общее количество работ по проекту: "; cin >> n; for (k=0;k<n;k++) { cout << "Вводите начало, конец дуги и продолжительность: "; cin >> i[k] >> j[k] >> dij[k]; } Critical_Path (n,&i[0],&j[0],&dij[0],&s1[0],&s2[0],&f1[0],&f2[0],&tf[0],&ff[0]); //Вывод результатов. cout << "Самый ранний срок начала : "; for (k=0;k<n;k++) cout << s1[k] << " "; cout << endl; cout << "Самый поздний срок начала : "; for (k=0;k<n;k++) cout << s2[k] << " "; cout << endl; cout << "Самый ранний срок завершения : "; for (k=0;k<n;k++) cout << f1[k] << " "; cout << endl; cout << "Самый поздний срок завершения : "; for (k=0;k<n;k++) cout << f2[k] << " "; cout << endl; cout << "Свободный резерв времени : "; for (k=0;k<n;k++) cout << ff[k] << " "; cout << endl; cout << "Полный резерв времени : "; for (k=0;k<n;k++) cout << tf[k] << " "; cout << endl; // Определение критического пути. Критический путь задается // стрелками, соединяющими события, для которых полный резерв // времени равен нулю. cout << "Критический путь: " << 1 << " "; for (k=0;k<n;k++) if ( tf[k]==0 ) cout << j[k] << " "; }
(1) Библиотека алгоритмов 1б-50б. (Справочное пособие.) - М.: Сов.радио, 1975. - 176 с.
На следующем шаге мы приведем программу вычисления потока в сети.
