Сверь числа и знаки с фото.
Этап 2: Обнови матрицу через вершину B
[Рисунок: вершины A, B, C; A сверху, B слева снизу, C справа снизу; рёбра A—B с весом 4, A—C с весом 10, B—C с весом 3.]
Матрица: A B C A 0 4 10 B 4 0 3 C 10 3 0
Краткий ответ: после шага через вершину \(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\).