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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 35: Строка 35:
 
| '''4''' || - || - || - || 0
 
| '''4''' || - || - || - || 0
 
|}
 
|}
Требуется найти путь из '''2''' в '''4'''.  
+
Требуется найти путь из '''2''' в '''4'''. <br />
Матрица p будет выглядеть следующим образом: <br />
+
Массив p будет выглядеть следующим образом: <br />
 
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
 
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
 
|-
 
|-
Строка 43: Строка 43:
 
| 2 || 1 || 3 || 4
 
| 2 || 1 || 3 || 4
 
|}
 
|}
Матрица d будет выглядеть следующим образом:  <br />
+
Массив d будет выглядеть следующим образом:  <br />
 
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
 
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
 
|-
 
|-

Версия 09:58, 29 ноября 2011

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

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

Решение

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

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

Так как мы обходим граф в порядке топологической сортировки, то на 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.

Источники