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

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Задача:

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

Решение

Воспользуемся принципом оптимальности на префиксе.
Пусть [math]d[/math] — функция, где [math]d(i)[/math] — вес кратчайшего пути из [math]u[/math] в [math]i[/math]. Ясно, что [math]d(u)[/math] равен [math]0[/math]. Пусть [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 — массив индексов вершин графа в порядке топологической сортировки
 for i = 1 .. n
   d[i] = [math]\infty[/math]
 d[u] = 0 // где u — начальная вершина

 p = topSort(w) //топологическая сортировка графа
 for i = 1 .. n
   for j: есть ребро из p[i] в j
     d[j] = min(d[j], d[p[i]] + w[p[i]][j]) 

Пример

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

Пусть дана матрица смежности графа [math]w[/math] со следующими весами ребер:

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

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

[math]i[/math]	1	2	3	4	5	6	7	8
[math]p[i][/math]	2	3	6	7	1	5	8	4

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

[math]i[/math]	1	2	3	4	5	6	7	8
[math]d[i][/math]	1	0	1	5	3	2	4	4

Ответ равен [math]5[/math].

Альтернативный способ решения

Решим задачу, используя обход в ширину. Для этого заведем массив, в котором будем хранить веса кратчайших расстояний от начальной вершины до всех остальных. Совершая обход по графу, будем в каждой вершине для всех ее потомков проверять, уменьшится ли вес кратчайшего пути до сына, если пройти через текущую вершину. Если да, то весу кратчайшего расстояния до сына присваиваем значение, равное сумме веса кратчайшего расстояния до текущей вершины и стоимости прохода по ребру между вершиной и ее сыном. В силу особенности обхода графа, обновление весов кратчайших путей до сыновей вершины происходит только тогда, когда для нее уже найден оптимальный ответ.

См. также

• Алгоритм Флойда—Уоршалла
• Алгоритм Форда-Беллмана

Источники информации

• Алгоритмы поиска кратчайшего пути в графе
• Wikipedia — Optimal substructure