Шаг 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