48
правок
Изменения
→Решение
{{Определение|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это такой путь из '''u '''в '''v''', что его вес меньше или равен веса любого другого пути из '''u''' в '''v'''}}
==Решение==
Пусть d — матрица, где d[i] — вес кратчайшего пути из '''u''' в '''i'''. Изначально значения d равны бесконечности, кроме d[u], который равен 0. Пусть w[i][j] - вес ребра из '''i''' в '''j'''. Будем обходить граф в порядке топологической сортировки. Получаем следующие соотношения: <br />
: <tex> d[i] = \min\limits_{\mathop{j:j \rightsquigarrow i}} (d[j] + w[j][i]) </tex>
