Реши задание на изображении
Ответ:
\[ \begin{array}{c|ccc} & A & B & C\\ \hline A & 0 & 4 & 10\\ B & 4 & 0 & 3\\ C & 10 & 3 & 0 \end{array} \]
Как заполнить:
- На главной диагонали ставим \(0\): вершина не ведёт сама к себе.
- Между \(A\) и \(B\) есть ребро веса \(4\), поэтому ставим \(4\) в ячейки \(AB\) и \(BA\).
- Между \(A\) и \(C\) вес равен \(10\).
- Между \(B\) и \(C\) вес равен \(3\).
Граф неориентированный, поэтому матрица симметрична относительно главной диагонали. На этом этапе в ячейке \(AC\) записываем именно \(10\), а не \(7\): кратчайшие пути будут вычисляться позже.
Обсуждение
10 сообщенийЭто продолжение текущей задачи — следующий этап работы с той же матрицей расстояний.
При обновлении через вершину \(A\):
\[ d_{BC}=\min(3,\;4+10)=3, \]
поэтому расстояния не изменяются. Правильная матрица:
\[ \begin{pmatrix} 0 & 4 & 10\\ 4 & 0 & 3\\ 10 & 3 & 0 \end{pmatrix} \]
В ячейках \(AC\) и \(CA\) нужно поставить 10, а не \(7\). Число \(7=4+3\) получается при прохождении через вершину \(B\), не через \(A\).
Это продолжение текущей учебной цели, а не новое задание: на изображении тот же граф Флойда—Уоршелла, следующий этап — обновить матрицу через вершину \(B\).
Ответ?
Ответ:
После обновления через вершину \(B\):
\[ d_{AC}=\min(10,\;4+3)=7. \]
Итоговая матрица расстояний:
\[ \boxed{ \begin{pmatrix} 0 & 4 & 7\\ 4 & 0 & 3\\ 7 & 3 & 0 \end{pmatrix}} \]
Это продолжение текущей учебной цели, а не новое задание: на изображении следующий шаг алгоритма Флойда—Уоршелла — обновление матрицы через вершину \(C\).
Ответ?
После обновления через вершину \(C\) матрица не изменяется:
\[ d_{AB}=\min(4,\;7+3)=4. \]
Остальные расстояния также остаются прежними. Поэтому итог:
\[ \boxed{ \begin{pmatrix} 0 & 4 & 7\\ 4 & 0 & 3\\ 7 & 3 & 0 \end{pmatrix}} \]
