Кратчайший путь в ациклическом графе
Пусть дан ациклический ориентированный взвешенный граф. Требуется найти вес кратчайшего пути из u в v
| Определение: |
| Кратчайший путь из u в v – это такой путь из u в v, что его сумарный вес входящих его ребер минимален |
Содержание
Решение
Пусть d — массив, где d[i] — вес кратчайшего пути из u в i. Изначально значения d равны бесконечности, кроме d[u], который равен 0. Пусть w[i][j] - вес ребра из i в j. Будем обходить граф в порядке топологической сортировки. Получаем следующие соотношения:
Так как мы обходим граф в порядке топологической сортировки, то на 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 | 0 | - | - | 5 | - | - | - | - |
| 2 | 1 | 0 | 1 | - | 4 | 3 | - | - |
| 3 | - | - | 0 | - | - | 1 | - | - |
| 4 | - | - | - | 0 | - | - | - | - |
| 5 | - | - | - | 3 | 0 | - | - | 1 |
| 6 | - | - | - | 5 | - | 0 | 2 | - |
| 7 | - | - | - | 2 | - | - | 0 | - |
| 8 | - | - | - | 1 | - | - | - | 0 |
Требуется найти путь из 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.
