Ветвь 1. Попарная проверка вершин и нахождение диаметра 11 страница
а б
Рис. 2.82. Пример сборки неориентированного нагруженного графа. Шаг 2;
а – граф G2; б – граф G1
1) Добавляем вершину 
, смежные ей вершины 
(рис. 2.83). Поскольку 
, 
, 
, 
и 
, то путей 
, 
, 
, 
и 
не существует. Пересчитываем значения весовых коэффициентов дуг, связывающих вершины из 
и 
, а также введем новые дуги, связывающие 
и 
, рассчитаем их весовые коэффициенты:
; j* = 2.
Элемент матрицы Р в ячейке 
, изменяется следующим образом: 
. Значение 
определено верно в начале алгоритма, поэтому не изменяется. Значения 
; 
известны. Далее
; j* = 2.
Пустой элемент матрицы Р в ячейке 
, изменяется следующим образом: 
. Значение 
.
; j* = 2.
Пустой элемент матрицы Р в ячейке 
, изменяется следующим образом: 
. Значение 
.
; j* = 2.
Пустой элемент матрицы Р в ячейке 
, изменяется следующим образом: 
. Значение 
.
| Матрица последователей P | Матрица кратчайших расстояний M | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
а б
|
|
|
Рис. 2.83. Пример сборки ориентированного нагруженного графа. Шаг 1;
а – граф G1; б – граф G0
В результате применения метода разборки-сборки графа получили матрицу кратчайших расстояний M и матрицу последователей P для минимальных путей.
Дата добавления: 2021-02-10; просмотров: 59; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!