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

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

Определение:

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

Решение

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

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

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

Реализация

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

 //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(); // запись данных

Пример

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

Пусть дан граф со следующими весами 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	1	5	3	2	4	4

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

Источники

• Алгоритмы поиска кратчайшего пути в графе
• Принцип оптимальности на префиксе
• Принцип оптимальности на подзадаче (в качестве примера разбирается задача поиска кратчайшего пути в ациклическом графе)(англ.)