Изменения

==Формулировка задачи={{Задача|definition =Пусть дан [[Основные_определения_теории_графов |ациклический ориентированный взвешенный граф]]. Требуется найти вес [[Алгоритм_Дейкстры |кратчайшего пути ]] из '''<tex>u''' </tex> в '''<tex>v''' </tex>. {{Определение|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это такой путь из '''u '''в '''v''', что его вес меньше или равен веса любого другого пути из '''u''' в '''v'''}} 

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

Так как мы обходим граф в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки |топологической сортировки]], то на <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, w {{--- матрицы как в описании, }} массив кратчайших расстояний</font> <font color=green>//p {{--- }} массив индексов вершин графа в порядке топологической сортировки, i, j - счетчики <br /> inputData() //считывание данных <br /font> '''for ''' i = 1 to .. n d[i] = infinity <br tex>\infty</tex> p d[u] = 0 <font color= topSort() green>//где u {{---}} начальная вершина</топологическая сортировка font><br /> d[p[u]] = 0 topSort(w) <font color=green>//топологическая сортировка графа<br /font> '''for ''' i = 1 to .. n '''for ''' j: /exist есть ребро из p[i] \rightsquigarrow в j

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

| || '''1''' || '''2''' || '''3''' || '''4'''|| '''5''' || '''6''' || '''7''' || '''8'''|-| '''1''' || - || - || - || - || 2 || - || - || - |-| '''2''' || 1 || - || 1 || - || 4 || 3 || - || - |-| '''3''' || - || - || - || - || - || 1 || - || - |-| '''4''' || - || - || - || - || - || - || - || -

| '''15''' || 0 - || - || - || 3 || - || - || - || 1

| '''26''' || 2 - || - || - || 5 || - || 0 - || 1 2 || -

| '''37''' || - || - || 0 - || 2 || 1 - || - || - || -

| '''48''' || - || - || - || 0 1 || - || - || - || -

Требуется найти путь вес кратчайшего пути из '''12''' в '''4'''. <br />Матрица Массив <tex>p </tex> будет выглядеть следующим образом: <br />

| <tex>i</tex> || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''

| <tex>p[i]</tex> || 2 || 3 || 6 || 7 || 1 || 3 5 || 8 || 4

Матрица Массив <tex>d </tex> будет выглядеть следующим образом: <br />

| <tex>i</tex> || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''

| <tex>d[i]</tex> || 1 || 0 || 1 || 5 || 3 || 2 || 24 || 4

Ответ равен 2<tex>5</tex>. ==Альтернативный способ решения==Решим задачу, используя [[Обход_в_ширину |обход в ширину]]. Для этого заведем массив, в котором будем хранить веса кратчайших расстояний от начальной вершины до всех остальных. Совершая обход по графу, будем в каждой вершине для всех ее потомков проверять, уменьшится ли вес кратчайшего пути до сына, если пройти через текущую вершину. Если да, то весу кратчайшего расстояния до сына присваиваем значение, равное сумме веса кратчайшего расстояния до текущей вершины и стоимости прохода по ребру между вершиной и ее сыном.В силу особенности обхода графа, обновление весов кратчайших путей до сыновей вершины происходит только тогда, когда для нее уже найден оптимальный ответ. ==См. также==*[[Алгоритм_Флойда_—_Уоршалла |Алгоритм Флойда—Уоршалла]]*[[Алгоритм_Форда-Беллмана |Алгоритм Форда-Беллмана]] ==Источникиинформации==* [http://enwww.ics.wikipediauci.orgedu/~eppstein/wiki161/Optimal_substructure Принцип оптимальности на подзадаче (в качестве примера разбирается задача 960208.html Алгоритмы поиска кратчайшего пути в ациклическом графе)(англ]* [http://en.wikipedia.)org/wiki/Optimal_substructure Wikipedia {{---}} Optimal substructure][[Категория:Дискретная математика и алгоритмы]][[Категория: Динамическое программирование ]]