48
правок
Изменения
→Решение
: <tex> d[i] = \min\limits_{\mathop{j:j \rightsquigarrow i}} (d[j] + w[j][i]) </tex>
Так как мы обходим граф в порядке топологической сортировки, то на i-ом шаге во всех d[j] (j такие, что: существует ребро из j в i) уже записаны оптимальные ответы, и следовательно в d[i] так же также будет записан оптимальный ответ.
==Реализация==
