48
правок
Изменения
Нет описания правки
{{Определение|definition= '''Кратчайший путь''' из '''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>
Так как мы обходим граф в порядке топологической сортировки, то на i-ом шаге во всех всем d[(j] ) (j такие, что: существует ребро из j в i) уже записаны присвоены оптимальные ответы, и следовательно в d[(i] ) также будет записан присвоен оптимальный ответ.
==Реализация==
Реализуем данный алгоритм следующим образом: рассмотрим вершину i. Будем пересчитывать d для всех вершин, выходящих из i:
//w - матрицы как в описании, d - массив как в описании, p - массив индексов вершин графа в порядке топологической сортировки, i, j - счетчики <br />
inputData() //считывание данных <br />
