Изменения

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

min \text{ } \omegaТак как мы обходим граф в порядке топологической сортировки, то на i-ом шаге во всех d[j] (p) \text{ for all ways p from u to v} &;if \text{ }\mathcal{9} p \\\mathcal{1}&;if \text{ } \nexists p\\\end{array}\right.<j такие, что: /tex>}}==Принцип оптимальности на префиксе==Префикс оптимального решения сам является оптимальным решением (exist ребро из j в другой подзадачеi)<br><tex>a \rightsquigarrow b \rightsquigarrow c </tex> <br>Если ac - оптимальное решение уже записаны оптимальные ответы, то и ab (префикс ac) тоже является оптимальным решениемследовательно в d[i] так же будет записан оптимальный ответ.<br>

== Реализация==Реализуем данный алгоритм методом "динамика вперед": //d, w - матрицы как в описании, p - матрица индексов вершин графа в порядке топологической сортировки, i, j - счетчики <br /> inputData() //считывание данных <br /> for i = 1 to n d[i] = infinity <br /> topSort() //топологическая сортировка <br /> d[p[u]] = 0 <br /> for i = 1 to n for j: /exist p[i] \rightsquigarrow j d[j] = min(d[j], d[p[i]] + w[p[i]][j]) <br /> writeData(); // запись данных

Для нахождения кратчайшего пути в графе заведем функцию переменную opt[x], в которой хранится длина кратчайшего пути до вершины х.<br>==Пример==В общем случае мы можем написатьПусть дан граф со следующими весами '''w''' ребер: <br/><tex>opt[u] {| class="wikitable" cellpadding="4" border="1" style= min_{v,u \in E"border-collapse: collapse;"|-| || '''1''' || '''2''' || '''3''' || '''4'''|-| '''1''' || 0 || 1 || 1 || 4|-| '''2''' || - || 0 || - || 2|-| '''3''' || - || - || 0 || 1|-| '''4''' || - || - || - || 0|} (opt[v] + cost(vu))</tex>, где cost(vu) - вес ребра Требуется найти путь из u '''1''' в v'''4'''. матрица d будет выглядеть следующим образом: <br/>Будем обходить вершины в порядке, обратном к топологической сортировке.{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"|-| '''1''' || '''2''' || '''3''' || '''4'''|-| 0 || 1 || 1 || 2|}