Изменения

Пусть <tex>d</tex> — функция, где <tex>d(i)</tex> — вес кратчайшего пути из <tex>u</tex> в <tex>i</tex>. Ясно, что <tex>d(u)</tex> равен <tex>0</tex>. Пусть <tex>w(i, j)</tex> - вес ребра из <tex>i</tex> в <tex>j</tex>. Будем обходить граф в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки | топологической сортировки]]. Получаем следующие соотношения: <br />

Так как мы обходим граф в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки |топологической сортировки]], то на <tex>i</tex>-ом шаге всем <tex>d(j)</tex> (<tex>j</tex> такие, что существует ребро из <tex>j</tex> в <tex>i</tex>) уже присвоены оптимальные ответы, и, следовательно, <tex>d(i)</tex> также будет присвоен оптимальный ответ.

<font color=green>//w {{--- матрицы как в описании, }} матрица смежности</font> <font color=green>//d {{- --}} массив как в описании, кратчайших расстояний</font> <font color=green>//p {{--- }} массив индексов вершин графа в порядке топологической сортировки, i, j - счетчики <br /> inputData() //считывание данных <br /font> '''for ''' i = 1 to .. n d[i] = '''infinity ''' d[u] = 0 <font color=green>// где u {{---}} начальная вершина</font><br /> p = topSort(w) <font color=green>//топологическая сортировка графа <br /> d[u] = 0 <br /font> '''for ''' i = 1 to .. n '''for ''' j: есть ребро из p[i] в j

[[Файл:Index1WayAcyclicGraph.jpgpng|thumb|right|180px500px|граф Граф из примера]]Пусть дан граф со следующими весами дана матрица смежности графа '''w''' со следующими весами ребер: <br />

==Альтернативный способ решения==Задачу так же можно решить [[Обход_в_ширину |поиском в ширину]]. Для этого будем поддерживать массив кратчайший расстояний от начальной до текущей вершины. Обходя граф, будем для каждой вершины обновлять ответы у ее сыновей как минимум из старого значения и пути, проходящего через текущую вершину. В силу особенности обхода графа, когда происходит обновление сыновей вершины, для нее самой уже найден оптимальный ответ. ==Смотри также==*[[Обход_в_ширину | Обход в ширину]]*[[Алгоритм_Флойда_—_Уоршалла |Алгоритм Флойда—Уоршалла]]*[[Алгоритм_Дейкстры |Алгоритм Дейкстры]]*[[Алгоритм_Форда-Беллмана |Алгоритм Форда-Беллмана]] ==Источникиинформации==