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

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

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

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

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

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

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

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

3) , ? Нет.

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

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

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

7) , ? Нет.

8) , ? Нет.

9) , ? Нет.

10) , ? Нет.

11) , ? Нет.

12) , ? Нет.

13) , ? Нет.

14) , ? Нет.

15) , ? Нет.

16) , ? Нет.

17) , ? Нет.

18) , ? Нет.

19) , ? Нет.

20) , ? Нет.

21) , ? Нет.

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

								Базовая строка 9

Базовый столбец

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

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

Поскольку ни один элемент базовой строки и базового столбца не равен , то в дальнейших расчетах используем .

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

1) , ? Нет.

2) , ? Нет.

3) , ? Нет.

4) , ? Нет.

5) , ? Нет.

6) , ? Нет.

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

8) , ? Нет.

9) , ? Нет.

10) , ? Нет.

11) , ? Нет.

12) , ? Нет.

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

14) , ? Нет.

15) , ? Нет.

16) , ? Нет.

17) , ? Нет.

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

19) , ? Нет.

20) , ? Нет.

21) , ? Нет.

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

23) , ? Нет.

24) , ? Нет.

25) , ? Нет.

26) , ? Нет.

27) , ? Нет.

28) , ? Нет.

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

								Базовая строка 9
								12

Базовый столбец

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

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