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