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

2013-12-17T20:06:07Z

Daria Yakovleva, 1539: /* Решение */

Пусть дан ациклический ориентированный взвешенный граф. Требуется найти вес кратчайшего пути из '''u''' в '''v'''
{{Определение|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это такой путь из '''u '''в '''v''', что его суммарный вес входящих в него ребер минимален}}
==Решение==
Пусть <tex>d</tex> — функция, где <tex>d(i)</tex> — вес кратчайшего пути из <tex>u</tex> в <tex>i</tex>. Ясно, что <tex>d(u)</tex> равен 0. Пусть <tex>w(i, j)</tex> - вес ребра из <tex>i</tex> в <tex>j</tex>. Будем обходить граф в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки | топологической сортировки]]. Получаем следующие соотношения: 
: <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> также будет присвоен оптимальный ответ.

==Реализация==
Реализуем данный алгоритм:
//w - матрицы как в описании, d - массив как в описании, p - массив индексов вершин графа в порядке топологической сортировки, i, j - счетчики 
inputData() //считывание данных 
for i = 1 to n
d[i] = infinity 
p = topSort(w) //топологическая сортировка графа 
d[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(); // запись данных

==Пример==
[[Файл:Index1.jpg|thumb|right|180px|граф из примера]]
Пусть дан граф со следующими весами '''w''' ребер: 
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| || '''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 будет выглядеть следующим образом: 
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''
|-
| 2 || 3 || 6 || 7 || 1 || 5 || 8 || 4
|}
Массив d будет выглядеть следующим образом: 
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''
|-
| 1 || 0 || 1 || 5 || 3 || 2 || 4 || 4
|}

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

==Источники==
*[http://www.ics.uci.edu/~eppstein/161/960208.html Алгоритмы поиска кратчайшего пути в графе]
*[[Динамическое_программирование#.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 Принцип оптимальности на подзадаче (в качестве примера разбирается задача поиска кратчайшего пути в ациклическом графе)(англ.)]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

Викиконспекты - Вклад участника [ru]

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