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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 65: Строка 65:
 
*[[Динамическое_программирование#.D0.9F.D1.80.D0.B8.D0.BD.D1.86.D0.B8.D0.BF_.D0.BE.D0.BF.D1.82.D0.B8.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8_.D0.BD.D0.B0_.D0.BF.D1.80.D0.B5.D1.84.D0.B8.D0.BA.D1.81.D0.B5|Принцип оптимальности на префиксе]]
 
*[[Динамическое_программирование#.D0.9F.D1.80.D0.B8.D0.BD.D1.86.D0.B8.D0.BF_.D0.BE.D0.BF.D1.82.D0.B8.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8_.D0.BD.D0.B0_.D0.BF.D1.80.D0.B5.D1.84.D0.B8.D0.BA.D1.81.D0.B5|Принцип оптимальности на префиксе]]
 
* [http://en.wikipedia.org/wiki/Optimal_substructure Принцип оптимальности на подзадаче (в качестве примера разбирается задача поиска кратчайшего пути в ациклическом графе)(англ.)]
 
* [http://en.wikipedia.org/wiki/Optimal_substructure Принцип оптимальности на подзадаче (в качестве примера разбирается задача поиска кратчайшего пути в ациклическом графе)(англ.)]
[[Категория: Динамическое программирование]] [[Категория: Дискретная математика и алгоритмы]]
+
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Динамическое программирование]]

Версия 23:32, 16 января 2012

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

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

Решение

Пусть d — функция, где d(i) — вес кратчайшего пути из u в i. Ясно, что 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 такие, что: существует ребро из j в i) уже присвоены оптимальные ответы, и следовательно d(i) также будет присвоен оптимальный ответ.

Реализация

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

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

Пример

граф из примера

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

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

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

1 2 3 4 5 6 7 8
2 3 6 7 1 5 8 4

Массив d будет выглядеть следующим образом:

1 2 3 4 5 6 7 8
1 0 3 5 3 2 4 4

Ответ равен 2.

Источники