Новая Школа - онлайн-школа подготовки к ЕГЭ
Задача Задача №3831721
А
Аноним
16 часов назад · публичный вопрос
А
Аноним

Этап 2: Обнови матрицу через вершину B

Запрос пользователя

Реши задание на изображении

Ответ нейросети
16 часов назад

Краткий ответ: после шага через вершину \(B\) матрица станет такой:

\[ \begin{array}{c|ccc} & A & B & C\\ \hline A & 0 & 4 & \mathbf{7}\\ B & 4 & 0 & 3\\ C & \mathbf{7} & 3 & 0 \end{array} \]

Изменились только две симметричные клетки: расстояние \(A-C\) и \(C-A\): было \(10\), стало \(7\).

Почему так:

На шаге через \(B\) для каждой пары вершин \(i,j\) проверяем, не короче ли путь \(i\to B\to j\):

\[ d_{ij}\leftarrow \min\bigl(d_{ij},\ d_{iB}+d_{Bj}\bigr). \]

Главная проверка здесь:

\[ d_{AB}+d_{BC}=4+3=7<10=d_{AC}. \]

То есть путь \(A\to B\to C\) короче прямого ребра \(A-C\). Поэтому записываем \(d_{AC}=7\). Граф неориентированный, значит \(d_{CA}=7\) тоже.

Остальные значения не улучшаются: например, \(B\to C\) через \(B\) даёт \(0+3=3\), а \(A\to B\) даёт \(4+0=4\).

Проверка: новый кратчайший путь из \(A\) в \(C\) идёт через \(B\) и имеет вес \(4+3=7\).