Маємо орієнтований граф G =(V, E), кожній дузі v à w цього графа відповідає невід’ємна ціна С [v, w]. Загальна задача знаходження найдовших шляхів полягає в знаходженні для кожної вершини впорядкованої пари вершин (v, w) любого шляху від вершини v до вершини w, довжина якого максимальна серед усіх можливих шляхів від v до w.

Існує прямий спосіб розв’язання цієї задачі, використовуючий алгоритм Флойда (R. W. Floyd).  Для визначеності установимо, що вершини графа послідовно пронумеровани від 1 до n. Алгоритм Флойда використовує матрицю А розміру nхn, в якій обчислюються довжини найдовших шляхів. На початку А[i, j]=C[i, j] для усіх i≠j. Якщо дуга i à j відсутня, то C[i, j]=-∞. Кожний діагональний елемент матриці А дорівнює 0.

Над матрицею А виконується n ітерацій. Після k-тої ітерації A[i, j] містить значення шляхів найменшої довжини з вершини i в вершину j, які не проходять через вершини з номером, більшим за k. Іншими словами, між кінцевими вершинами шляху i и j можуть знаходитися вершини, номера яких менше чи рівні k.

На k-тій ітерації для обчислення матриці А застосовується наступна формула:

A_k[i, j] = min(A_k-1[i, j], A_k-1[i, k] + A_k-1[k, j]).

Нижній індекс k позначає значення матриці А після k-тої ітерації, однак це означає, що існує n різних матриць, цей індекс використовується для скорочення запису.

Для обчислення A_k[i, j] проводиться порівняння вершини A_k-1[i, j] (тобто ціна от шляху від вершини i до вершини j без участі вершини k чи іншої вершини з більш високим номером) з величиною A_k-1[i, k] + A_k-1[k, j] (ціна шляху від вершини i до вершини k плюс шляху від вершини k до вершини j). Якщо шлях через вершину k дорожче, ніж A_k-1[i, j], то величина A_k[i, j] змінюється.

Рівності A_k[i, k] = A_k-1[i, k] и A_k[k, j] = A_k-1[k, j] означають, що на k-тій ітерації елементи матриці А, що стоять в k-тій строці и в k-м стовпці, не змінюються. Усі обчислення можливо проводити лише з однією копією матриці А.

Щоб встановити при необхідності найдорожчі шляхи, можна в алгоритмі Флойда ввести ще одну матрицю P, в якій елемент P [i, j] містить вершину k, отриману при знаходженні найбільшого значення A[i, j]. Якщо P[i, j] = 0, то найдовший шлях з вершини i в вершину j складається з однієї дуги i à j.

Модифікована версія алгоритму Флойда, що дозволяє відновити найдовші шляхи:

private void AlgorithmFloyda(double [,]C, int [,]P)

{

int i,j,k;

int nn = (int)Math.Sqrt(C.Length)-1;

double [,]A = new double[nn+1,nn+1];

for(i=1; i<=nn; i++)

       for(j=1; j<=nn; j++)

       {

            A[i,j] = C[i,j];

            P[i,j] = 0;

       }

for(i=1; i<=nn; i++)

       A[i,i] = 0;

for(k=1; k<=nn; k++)

       for(i=1; i<=nn; i++)

            for(j=1; j<=nn; j++)

                 if(A[i,k] + A[k,j] >A[i,j])

                 {

                      A[i,j]=A[i,k]+A[k,j];

                      P[i,j]=k;

                 }

}

Програма повинна виконувати топологічний аналіз СГ на існування обривів та контурів. Якщо у СГ існує i-та вершина, з якої не виходить жодна дуга-робота (тобто i-й рядок матриці містить лише від’ємні числа), то знайден обрив. Тоді вершина, що висить, видаляється з графа шляхом заміни i-го стовпця матриці числами, що символізують - ¥. Повідомлення про відповідні дії будуть записуватися у вихідний файл. Аналіз на існування контурів буде проводиться під час знаходження максимального шляху між вершинами: СГ є топологічно відсортованим, тому виявлення зворотної дуги v à w (v>w) свідчить про наявність контуру. У цьому разі для попередження зациклювання виконання програми буде припинятися.

Розрахунок часових параметрів проекту буде виконуватися на основі наведеного алгоритму Флойда, що знаходить найдовші шляхи між парами вершин.

Застосовуючи цей алгоритм до прямої/інвертованної матриці СГ, можна отримати дані про шляхи максимальної тривалості, що передують кожній події/ слідують за кожною подією.

Розрахунок критичного шляху, визначення ранніх і пізніх термінів настання подій, ранніх і пізніх термінів початку і завершення робіт, повних и вільних резервів часу виконання робіт буде виконуватися на базі інформації, отриманої алгоритмом Флойда, за формулами, що наведенні в I розділі.

Результати розрахунків будуть записуватися до файлу у вигляді таблиць, що містять часові параметри СГ.

Також програма буде формувати графічне представлення СГ - діаграму Ганта. На діаграмі кожній роботі буде відповідати два часових параметра: безпосередньо тривалість роботи та її повний резерв.

Структура файлу вхідних даних: кожній роботі графа буде відповідати рядок, що складається з двох цілих та одного/двох дійсних чисел, вигляду

i j Назва роботи C_min C_max.