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

Краткий ответ: неверна только ячейка \(Y \to X\). Между \(Y\) и \(X\) есть путь \(Y\to Z\to X\) стоимостью \(1\).

Итоговая матрица кратчайших путей:

\[ \begin{array}{c|rrrr} & X & Y & Z & W\\ \hline X & 0 & 2 & -1 & -3\\ Y & 1 & 0 & -3 & -5\\ Z & 4 & 6 & 0 & -2\\ W & \infty & \infty & \infty & 0 \end{array} \]

Как получаются новые значения

Алгоритм Флойда—Уоршелла проверяет, выгоднее ли идти напрямую или через промежуточную вершину:

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

• Из \(Y\) в \(X\):

\[ Y\to Z\to X:\quad -3+4=1. \]

Поэтому вместо \(\infty\) записываем \(1\).

• Из \(Z\) в \(Y\):

\[ Z\to X\to Y:\quad 4+2=6. \]

• Из \(X\) в \(W\):

\[ X\to Z\to W:\quad -1+(-2)=-3. \]

• Из \(Y\) в \(W\):

\[ Y\to Z\to W:\quad -3+(-2)=-5. \]

Значок \(\infty\) означает отсутствие прямого обмена, но маршрут через другие валюты может существовать. Диагональ осталась нулевой, значит отрицательного цикла нет.