Шаг 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).
| ||||||||||
|
Рисунок 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).
| ||||||||||
12 | ||||||||||
|
Рисунок 8.15 ― Матрицы путей и переходов графа G перед началом шага p=5