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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 21: Строка 21:
  
 
==Пример==
 
==Пример==
[[Файл:Index.jpg|thumb|right|180px|граф из примера]]
+
[[Файл:Index1.jpg|thumb|right|180px|граф из примера]]
 
Пусть дан граф со следующими весами '''w''' ребер: <br />
 
Пусть дан граф со следующими весами '''w''' ребер: <br />
 
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
 
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
 
|-
 
|-
| || '''1''' || '''2''' || '''3''' || '''4'''
+
| || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''
 
|-
 
|-
| '''1''' || 0 || - || - || 1
+
| '''1''' || 0 || - || - || 5  ||  -  ||  -  ||  -  ||  -
 
|-
 
|-
| '''2''' || 2 || 0 || 1 || 3
+
| '''2''' || || 0 || 1 || -  ||  4  ||  3 ||  -  ||  -
 
|-
 
|-
| '''3''' || - || - || 0 || 1
+
| '''3''' || - || - || 0 || -  ||  -  ||  1 ||  -  ||  -
 
|-
 
|-
| '''4''' || - || - || - || 0
+
| '''4''' || - || - || - || 0  ||  -  ||  -  ||  -  ||  -
 +
|-
 +
| '''5''' ||  -  ||  -  ||  -  ||  3  ||  0  ||  -  ||  -  ||  1
 +
|-
 +
| '''6''' ||  -  ||  -  ||  -  ||  5  ||  -  ||  0  ||  2  ||  -
 +
|-
 +
| '''7''' ||  -  ||  -  ||  -  ||  2  ||  -  ||  -  ||  0  ||  -
 +
|-
 +
| '''8''' ||  -  ||  -  ||  -  ||  1  ||  -  ||  -  ||  -  ||  0  
 
|}
 
|}
 
Требуется найти путь из '''2''' в '''4'''. <br />
 
Требуется найти путь из '''2''' в '''4'''. <br />
Строка 39: Строка 47:
 
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
 
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
 
|-
 
|-
| '''1''' || '''2''' || '''3''' || '''4'''
+
| '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''
 
|-
 
|-
| 2 || 1 || 3 || 4
+
| 2 || 3 || 6 || 7 || 1 || 5 || 8 || 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;"
 
|-
 
|-
| '''1''' || '''2''' || '''3''' || '''4'''
+
| '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''
 
|-
 
|-
| 1 || 0 || 2 || 2
+
| 1 || 0 || 3 || 5 || 3 || 2 || 4 || 4
 
|}
 
|}
  

Версия 06:51, 16 января 2012

Пусть дан ациклический ориентированный взвешенный граф. Требуется найти вес кратчайшего пути из 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 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.

Источники