Кратчайший путь в ациклическом графе — различия между версиями
IRomchig (обсуждение | вклад) (→Реализация) |
|||
| Строка 1: | Строка 1: | ||
Пусть дан ациклический ориентированный взвешенный граф. Требуется найти вес кратчайшего пути из '''u''' в '''v''' | Пусть дан ациклический ориентированный взвешенный граф. Требуется найти вес кратчайшего пути из '''u''' в '''v''' | ||
| − | {{Определение|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это такой путь из '''u '''в '''v''', что его вес | + | {{Определение|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это такой путь из '''u '''в '''v''', что его сумарный вес входящих его ребер минимальен}} |
==Решение== | ==Решение== | ||
| − | Пусть d — массив, где d[i] — вес кратчайшего пути из u в i. Изначально значения d равны бесконечности, кроме d[u], который равен 0. Пусть w[i][j] - вес ребра из i в j. Будем обходить граф в порядке топологической сортировки. Получаем следующие соотношения: <br /> | + | Пусть d — массив, где d[i] — вес кратчайшего пути из u в i. Изначально значения d равны бесконечности, кроме d[u], который равен 0. Пусть w[i][j] - вес ребра из i в j. Будем обходить граф в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки | топологической сортировки]]. Получаем следующие соотношения: <br /> |
: <tex> d[i] = \min\limits_{\mathop{j:j \rightsquigarrow i}} (d[j] + w[j][i]) </tex> | : <tex> d[i] = \min\limits_{\mathop{j:j \rightsquigarrow i}} (d[j] + w[j][i]) </tex> | ||
| Строка 8: | Строка 8: | ||
==Реализация== | ==Реализация== | ||
| − | Реализуем данный алгоритм | + | Реализуем данный алгоритм: |
//w - матрицы как в описании, d - массив как в описании, p - массив индексов вершин графа в порядке топологической сортировки, i, j - счетчики <br /> | //w - матрицы как в описании, d - массив как в описании, p - массив индексов вершин графа в порядке топологической сортировки, i, j - счетчики <br /> | ||
inputData() //считывание данных <br /> | inputData() //считывание данных <br /> | ||
Версия 04:57, 16 января 2012
Пусть дан ациклический ориентированный взвешенный граф. Требуется найти вес кратчайшего пути из 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 | |
| 1 | 0 | - | - | 1 |
| 2 | 2 | 0 | 1 | 3 |
| 3 | - | - | 0 | 1 |
| 4 | - | - | - | 0 |
Требуется найти путь из 2 в 4.
Массив p будет выглядеть следующим образом:
| 1 | 2 | 3 | 4 |
| 2 | 1 | 3 | 4 |
Массив d будет выглядеть следующим образом:
| 1 | 2 | 3 | 4 |
| 1 | 0 | 2 | 2 |
Ответ равен 2.
