Реферат Мережеві графіки

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

Таблиця результатів роботи алгоритму.

n

1

2

3

4

5

6

7

8

9

10

11

РНАЧ (v)

0

0

5

35

35

50

55

65

68

65

71

РВИП (v)

0

5

35

50

47

55

65

68

71

68

71

Отримали, що мінімальний час, необхідну виконання проекту одно Т = РВИП (11), Т = 71. Тепер знайдемо допомогою алгоритму 2 значення часу найбільш пізнього початку і виконання робіт. Роботу алгоритму викладемо у вигляді послідовності виконуваних кроків. br/>

Крок n

Дії виконуються кроком

1

Оголошення значень ПВИП (v), vГЋV рівним Т.

Поточна вершина v k = 11.

2

ПНАЧ (11) = ПВИП (11)-t (11) {ПНАЧ (11) стало рівним 71}.

3

ПВИП (9) = МІН {ПВИП (9), ПНАЧ (11)} {ПВИП (9) стало рівним 71}

ПВИП (10) = МІН {ПВИП (10), ПНАЧ (11)} {ПВИП (10) стало рівним 71}

4

Поточна вершина v k = 10.

5

Перехід в Крок 2.

2

ПНАЧ (10) = ПВИП (10)-t (10) {ПНАЧ (10) стало рівним 68}

3

ПВИП (7) = МІН {ПВИП (7), ПНАЧ (10)} {ПВИП (7) стало рівним 68}

4

Поточна вершина v k = 9.

5

Перехід в Крок 2.

2

ПНАЧ (9) = ПВИП (9)-t (9) {ПНАЧ (9) стало рівним 68}

3

ПВИП (8) = МІН {ПВИП (8), ПНАЧ (9)} {ПВИП (8) стало рівним 68}

4

Поточна вершина v k = 8.

5

Перехід в Крок 2.

2

ПНАЧ (8) = ПВИП (8)-t (8) {ПНАЧ (8) стало рівним 65}

3

ПВИП (7) = МІН {ПВИП (7), ПНАЧ (8)} {ПВИП (7) стало рівним 65}

4

Поточна вершина v k = 7.

5

Перехід в Крок 2.

2

ПНАЧ (7) = ПВИП (7)-t (7) {ПНАЧ (7) стало рівним 55}

3

ПВИП (5) = МІН {ПВИП (5), ПНАЧ (7)} {ПВИП (5) стало рівним 55}

ПВИП (6) = МІН {ПВИП (6), ПНАЧ (7)} {ПВИП (6) стало рівним 55}

4

Поточна вершина v k = 6.

5

Перехід в Крок 2.

2

ПНАЧ (6) = ПВИП (6)-t (6) {ПНАЧ (6) стало рівним 50}

3

ПВИП (4) = МІН {ПВИП (4), ПНАЧ (6)} {ПВИП (5) стало рівним 50}

4

Поточна вершина v k = 5.

5

Перехід в Крок 2.

2

ПНАЧ (5) = ПВИП (5)-t (5) {ПНАЧ (5) стало рівним 43}

3

ПВИП (3) = МІН {ПВИП (3), ПНАЧ (5)} {ПВИП (3) стало рівним 43}

4

Поточна вершина v k = 4.

5

Перехід в Крок 2.

2

ПНАЧ (4) = ПВИП (4)-t (4) {ПНАЧ (4) стало рівним 35}

3