Кратчайший путь в ациклическом графе — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
−
{{Определение|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это любой путь '''p''' из '''u '''в '''v''', для которого <tex> w(p) = \delta(u, v)</tex>, где: <br>
+
==Формулировка задачи==
−
* <tex>\boldsymbol w(p) </tex> = сумма весов всех ребер пути p
+
Пусть дан ациклический взвешенный граф. Требуется найти вес кратчайшего пути из '''u''' в '''v'''
−
*<tex>\rm{\delta}(u, v) = \left\{\begin{array}{llcl}
+
{{Определение|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>
  
−
min \text{ } \omega(p) \text{ for all ways p from u to v} &;if  \text{ }\mathcal{9} p  \\
+
Так как мы обходим граф в порядке топологической сортировки, то на i-ом шаге во всех d[j] (j такие, что: /exist ребро из j в i) уже записаны оптимальные ответы, и следовательно в d[i] так же будет записан оптимальный ответ.
−
\mathcal{1}&;if \text{ } \nexists p\\
 
−
\end{array}\right.
 
−
</tex>
 
−
}}
 
−
==Принцип оптимальности на префиксе==
 
−
Префикс оптимального решения сам является оптимальным решением (в другой подзадаче)<br>
 
−
<tex>a \rightsquigarrow b \rightsquigarrow c </tex>  <br>
 
−
Если ac - оптимальное решение , то и ab (префикс ac) тоже является оптимальным решением.<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>
+
==Пример==
−
В общем случае мы можем написать: <br>
+
Пусть дан граф со следующими весами '''w''' ребер: <br />
−
<tex>opt[u] = min_{v,u \in E} (opt[v] + cost(vu))</tex>, где  cost(vu) - вес ребра из u в v.  <br>
+
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
−
Будем обходить вершины в порядке, обратном к топологической сортировке.
+
|-
 +
| || '''1''' || '''2''' || '''3''' || '''4'''
 +
|-
 +
| '''1''' || 0 || 1 || 1 || 4
 +
|-
 +
| '''2''' || - || 0 || - || 2
 +
|-
 +
| '''3''' || - || - || 0 || 1
 +
|-
 +
| '''4''' || - || - || - || 0
 +
|}
 +
Требуется найти путь из '''1''' в '''4'''. матрица d будет выглядеть следующим образом: <br />
 +
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
 +
|-
 +
| '''1''' || '''2''' || '''3''' || '''4'''
 +
|-
 +
| 0 || 1 || 1 || 2
 +
|}
  
 +
Ответ будет равен 2.
 +
==Источники==
 +
* [http://ru.wikipedia.org/wiki/Динамическое_программирование Википедия]
 
[[Категория: Динамическое программирование ]]
 
[[Категория: Динамическое программирование ]]

Версия 09:45, 28 ноября 2011

Формулировка задачи

Пусть дан ациклический взвешенный граф. Требуется найти вес кратчайшего пути из u в v

Определение:
Кратчайший путь из u в v – это такой путь из u в v, что его вес меньше или равен веса любого другого пути из u в v

Решение

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

  • [math] d[i] = \min\limits_{\mathop{j:j \rightsquigarrow i}} (d[j] + w[j][i]) [/math]

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

Реализация

Реализуем данный алгоритм методом "динамика вперед": 

 //d, w - матрицы как в описании, p - матрица индексов вершин графа в порядке топологической сортировки, i, j - счетчики 

 inputData() //считывание данных 

 for i = 1 to n
   d[i] = infinity 

 topSort() //топологическая сортировка 

 d[p[u]] = 0 

 for i = 1 to n
   for j: /exist p[i] \rightsquigarrow j
     d[j] = min(d[j], d[p[i]] + w[p[i]][j]) 

 writeData(); // запись данных

Пример

Пусть дан граф со следующими весами w ребер:

1 2 3 4
1 0 1 1 4
2 - 0 - 2
3 - - 0 1
4 - - - 0

Требуется найти путь из 1 в 4. матрица d будет выглядеть следующим образом:

1 2 3 4
0 1 1 2

Ответ будет равен 2.

Источники

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Кратчайший_путь_в_ациклическом_графе&oldid=13592»