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

Краткий ответ

Третья итерация — промежуточная вершина \(2\):

\[ \begin{pmatrix} 0&5&10&8\\ \boxed{2}&\boxed{0}&\boxed{5}&\boxed{3}\\ -3&2&0&5\\ \boxed{-8}&\boxed{-3}&\boxed{-5}&\boxed{0} \end{pmatrix} \]

Итоговая матрица — промежуточная вершина \(3\):

\[ \begin{pmatrix} 0&5&3&8\\ \boxed{-5}&\boxed{0}&\boxed{-2}&\boxed{3}\\ -3&2&0&5\\ -8&-3&-5&0 \end{pmatrix} \]

Ключевой принцип

На каждой итерации проверяем, станет ли путь короче через выбранную промежуточную вершину:

\[ d_{ij}=\min\left(d_{ij},\ d_{ik}+d_{kj}\right). \]

3-я итерация: через вершину \(2\)

Для строки \(1\):

\[ d_{10}=\min(\infty,5+(-3))=2, \]

\[ d_{11}=\min(0,5+2)=0, \]

\[ d_{12}=5,\qquad d_{13}=\min(3,5+5)=3. \]

Получаем строку:

\[ (2,\ 0,\ 5,\ 3). \]

Для строки \(3\):

\[ d_{30}=\min(2,-5+(-3))=-8, \]

\[ d_{31}=\min(7,-5+2)=-3, \]

\[ d_{32}=-5,\qquad d_{33}=\min(0,-5+5)=0. \]

Получаем строку:

\[ (-8,\ -3,\ -5,\ 0). \]

4-я итерация: через вершину \(3\)

Для строки \(1\):

\[ d_{10}=\min(2,3+(-8))=-5, \]

\[ d_{11}=\min(0,3+(-3))=0, \]

\[ d_{12}=\min(5,3+(-5))=-2, \]

\[ d_{13}=3. \]

Проверка: например, путь \(0\to2\) через вершину \(3\) имеет длину

\[ 0\to3\to2:\quad 8+(-5)=3, \]

а \(3<10\), поэтому в итоговой матрице стоит \(3\).