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

Краткий ответ: итоговая матрица наиболее выгодных путей:

\[ \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} \]

Строка — начальная валюта, столбец — конечная.

Ключевой принцип алгоритма Флойда—Уоршелла

Для каждой промежуточной вершины \(k\) проверяем:

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

То есть сравниваем прямой путь с путём через промежуточную валюту.

Основные улучшения:

• Через \(X\):

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

• Через \(Y\):

\[ X\to W: \quad 2+1=3. \]

• Через \(Z\):

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

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

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

Например, самый выгодный путь из \(Y\) в \(W\):

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

Из \(W\) в другие валюты попасть нельзя, поэтому там остаются \(\infty\). На главной диагонали остались нули, значит отрицательного цикла нет.