Шаг 2 расчетов по алгоритму Флойда

Шаг 1 расчетов по алгоритму Флойда

Принимаем p=1. Принимаем в матрице вершину за базовую и выделяем базовую строку и базовый столбец (рис. 8.6).

Вычеркиваем в матрице строки и столбцы, базовые элементы которых имеют значение . В итоге получаем , изображенную на рис. 8.7.

Рисунок 8.7 ― Матрица после вычеркивания строк и столбцов, базовые элементы которых имеют значение

Изобразим на рис. 8.8 граф по матрице .

Рисунок 8.8 ― Граф

Выполним необходимые расчеты:

1) ? Т.е.? Да.

Тогда:

2) ? Т.е. ? Да.

Тогда:

3) ? Т.е.? Нет.

Тогда: .

4) ? Т.е. ? Нет.

Тогда:

5) ? Т.е. ? Да.

Тогда:

Вносим изменения в матрицы и (рис. 8.9).

Рисунок 8.9 ― Матрицы путей и переходов графа G перед началом шага p=2

Принимаем p=2. Принимаем в матрице вершину за базовую и выделяем базовую строку и базовый столбец (рис. 8.9).

Вычеркиваем в матрице строки и столбцы, базовые элементы которых имеют значение .

В итоге получаем матрицу , изображенную на рис. 8.10.

Рисунок 8.10 ― Матрица после вычеркивания строк и столбцов, базовые элементы которых имеют значение

Изобразим на рисунке 8.11 граф по матрице .

Рисунок 8.11 ― Граф

Выполним необходимые расчеты:

1) , ? Нет.

2) ,? Нет.

3) ,? Нет.

4) , ? Да. Тогда: .

5) , ? Да. Тогда: .

6) , ? Да. Тогда: .

7) , ? Нет.

8) , ? Да. Тогда: .

9) , ? Да. Тогда: .

10) , ? Да. Тогда:..

11) , ? Да. Тогда: .

12) ,? Нет.

13) ,? Нет.

14) ,? Нет.

15) ,? Нет.

16) ,? Да. Тогда: .

17) ,? Да. Тогда: .

18) ,? Нет.

19) ,? Нет.

20) ,? Да. Тогда: .

21) ,? Нет.

Вносим изменения в матрицы и (рис. 8.12).

Рисунок 8.12 ― Матрицы путей и переходов графа G перед началом шага p=3

Дата добавления: 2014-10-31