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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение)
м (rollbackEdits.php mass rollback)
 
(не показано 30 промежуточных версий 10 участников)
Строка 1: Строка 1:
==Формулировка задачи==
+
{{Задача
Пусть дан ациклический взвешенный граф. Требуется найти вес кратчайшего пути из '''u''' в '''v'''
+
|definition =  
{{Определение|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это такой путь из '''u '''в '''v''', что его вес меньше или равен веса любого другого пути из '''u''' в '''v'''}}
+
Пусть дан [[Основные_определения_теории_графов |ациклический ориентированный взвешенный граф]]. Требуется найти вес [[Алгоритм_Дейкстры |кратчайшего пути]] из <tex>u</tex> в <tex>v</tex>.
 +
}}
 +
 
 
==Решение==
 
==Решение==
Пусть d — матрица, где d[i] — вес кратчайшего пути из '''u''' в '''i'''. Изначально значения d равны бесконечности, кроме d[u], который равен 0. Пусть w[i][j] - вес ребра из '''i''' в '''j'''. Будем обходить граф в порядке топологической сортировки. Получаем следующие соотношения: <br />
+
Воспользуемся принципом оптимальности на префиксе.<br />
: <tex> d[i] = \min\limits_{\mathop{j:j \rightsquigarrow i}} (d[j] + w[j][i]) </tex>
+
Пусть <tex>d</tex> функция, где <tex>d(i)</tex> — вес кратчайшего пути из <tex>u</tex> в <tex>i</tex>. Ясно, что <tex>d(u)</tex> равен <tex>0</tex>. Пусть <tex>w(i, j)</tex> {{---}} вес ребра из <tex>i</tex> в <tex>j</tex>. Будем обходить граф в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки | топологической сортировки]]. Получаем следующие соотношения: <br />
 +
: <tex> d(i) = \min\limits_{\mathop{j:j \rightsquigarrow i}} (d(j) + w(j, i)) </tex>
  
Так как мы обходим граф в порядке топологической сортировки, то на i-ом шаге во всех d[j] (j такие, что: существует ребро из j в i) уже записаны оптимальные ответы, и следовательно в d[i] так же будет записан оптимальный ответ.
+
Так как мы обходим граф в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки |топологической сортировки]], то на <tex>i</tex>-ом шаге всем <tex>d(j)</tex> (<tex>j</tex> такие, что существует ребро из <tex>j</tex> в <tex>i</tex>) уже присвоены оптимальные ответы, и, следовательно, <tex>d(i)</tex> также будет присвоен оптимальный ответ.
  
 
==Реализация==
 
==Реализация==
Реализуем данный алгоритм методом "динамика вперед":
+
Реализуем данный алгоритм:
   //d, w - матрицы как в описании, p - массив индексов вершин графа в порядке топологической сортировки, i, j - счетчики <br />
+
   <font color=green>//w {{---}} матрица смежности</font>
  inputData() //считывание данных <br />
+
  <font color=green>//d {{---}} массив кратчайших расстояний</font>
   for i = 1 to n
+
  <font color=green>//p {{---}} массив индексов вершин графа в порядке топологической сортировки</font>
     d[i] = infinity <br />
+
   '''for''' i = 1 .. n
   p = topSort() //топологическая сортировка <br />
+
     d[i] = <tex>\infty</tex>
   d[p[u]] = 0 <br />
+
   d[u] = 0 <font color=green>// где u {{---}} начальная вершина</font><br />
   for i = 1 to n
+
   p = topSort(w) <font color=green>//топологическая сортировка графа</font>
     for j: /exist p[i] \rightsquigarrow j
+
   '''for''' i = 1 .. n
 +
     '''for''' j: есть ребро из p[i] в j
 
       d[j] = min(d[j], d[p[i]] + w[p[i]][j]) <br />
 
       d[j] = min(d[j], d[p[i]] + w[p[i]][j]) <br />
  writeData(); // запись данных
 
  
 
==Пример==
 
==Пример==
[[Файл:Graph_anticycle.jpg|thumb|right|180px|граф из примера]]
+
[[Файл:WayAcyclicGraph.png|thumb|right|500px|Граф из примера]]
Пусть дан граф со следующими весами '''w''' ребер: <br />
+
Пусть дана матрица смежности графа <tex>w</tex> со следующими весами ребер: <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''' ||  -  ||  -  ||  -  ||  -  ||  2  ||  -  ||  -  ||  -
 +
|-
 +
| '''2''' ||  1  ||  -  ||  1  ||  -  ||  4  ||  3  ||  -  ||  -
 +
|-
 +
| '''3''' ||  -  ||  -  ||  -  ||  -  ||  -  ||  1  ||  -  ||  -
 +
|-
 +
| '''4''' ||  -  ||  -  ||  -  ||  -  ||  -  ||  -  ||  -  ||  -
 
|-
 
|-
| '''1''' || 0 || - || - || 1
+
| '''5''' || -  ||  -  ||  -  ||  3  ||  -  || - || - || 1  
 
|-
 
|-
| '''2''' || 2 || 0 || 1 || -
+
| '''6''' || -  ||  -  ||  -  ||  5  ||  -  || || || -  
 
|-
 
|-
| '''3''' || - || - || 0 || 1
+
| '''7''' || - || - || -  ||  2  || -  ||  -  ||  -  ||  -
 
|-
 
|-
| '''4''' || - || - || - || 0
+
| '''8''' || - || - || - || 1  ||  -  ||  -  ||  -  ||  -
 
|}
 
|}
Требуется найти путь из '''1''' в '''4'''.  
+
Требуется найти вес кратчайшего пути из '''2''' в '''4'''. <br />
Матрица p будет выглядеть следующим образом: <br />
+
Массив <tex>p</tex> будет выглядеть следующим образом: <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'''
+
| <tex>i</tex> || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''
 
|-
 
|-
| 2 || 1 || 3 || 4
+
| <tex>p[i]</tex> || 2 || 3 || 6 || 7 || 1 || 5 || 8 || 4
 
|}
 
|}
Матрица d будет выглядеть следующим образом:  <br />
+
Массив <tex>d</tex> будет выглядеть следующим образом:  <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'''
+
| <tex>i</tex> || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''
 
|-
 
|-
| 1 || 0 || 2 || 2
+
| <tex>d[i]</tex> || 1 || 0 || 1 || 5 || 3 || 2 || 4 || 4
 
|}
 
|}
  
Ответ равен 2.
+
Ответ равен <tex>5</tex>.
==Источники==
+
 
* [http://en.wikipedia.org/wiki/Optimal_substructure Принцип оптимальности на подзадаче (в качестве примера разбирается задача поиска кратчайшего пути в ациклическом графе)(англ.)]
+
==Альтернативный способ решения==
[[Категория: Динамическое программирование ]]
+
Решим задачу, используя [[Обход_в_ширину |обход в ширину]]. Для этого заведем массив, в котором будем хранить веса кратчайших расстояний от начальной вершины до всех остальных. Совершая обход по графу, будем в каждой вершине для всех ее потомков проверять, уменьшится ли вес кратчайшего пути до сына, если пройти через текущую вершину. Если да, то весу кратчайшего расстояния до сына присваиваем значение, равное сумме веса кратчайшего расстояния до текущей вершины и стоимости прохода по ребру между вершиной и ее сыном.
 +
В силу особенности обхода графа, обновление весов кратчайших путей до сыновей вершины происходит только тогда, когда для нее уже найден оптимальный ответ.
 +
 
 +
==См. также==
 +
*[[Алгоритм_Флойда_—_Уоршалла |Алгоритм Флойда—Уоршалла]]
 +
*[[Алгоритм_Форда-Беллмана |Алгоритм Форда-Беллмана]]
 +
 
 +
==Источники информации==
 +
*[http://www.ics.uci.edu/~eppstein/161/960208.html Алгоритмы поиска кратчайшего пути в графе]
 +
* [http://en.wikipedia.org/wiki/Optimal_substructure Wikipedia {{---}} Optimal substructure]
 +
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Динамическое программирование]]

Текущая версия на 19:14, 4 сентября 2022

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


Решение

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

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

Так как мы обходим граф в порядке топологической сортировки, то на [math]i[/math]-ом шаге всем [math]d(j)[/math] ([math]j[/math] такие, что существует ребро из [math]j[/math] в [math]i[/math]) уже присвоены оптимальные ответы, и, следовательно, [math]d(i)[/math] также будет присвоен оптимальный ответ.

Реализация

Реализуем данный алгоритм:

 //w — матрица смежности
 //d — массив кратчайших расстояний 
 //p — массив индексов вершин графа в порядке топологической сортировки
 for i = 1 .. n
   d[i] = [math]\infty[/math]
 d[u] = 0 // где u — начальная вершина
p = topSort(w) //топологическая сортировка графа for i = 1 .. n for j: есть ребро из p[i] в j d[j] = min(d[j], d[p[i]] + w[p[i]][j])

Пример

Граф из примера

Пусть дана матрица смежности графа [math]w[/math] со следующими весами ребер:

1 2 3 4 5 6 7 8
1 - - - - 2 - - -
2 1 - 1 - 4 3 - -
3 - - - - - 1 - -
4 - - - - - - - -
5 - - - 3 - - - 1
6 - - - 5 - - 2 -
7 - - - 2 - - - -
8 - - - 1 - - - -

Требуется найти вес кратчайшего пути из 2 в 4.
Массив [math]p[/math] будет выглядеть следующим образом:

[math]i[/math] 1 2 3 4 5 6 7 8
[math]p[i][/math] 2 3 6 7 1 5 8 4

Массив [math]d[/math] будет выглядеть следующим образом:

[math]i[/math] 1 2 3 4 5 6 7 8
[math]d[i][/math] 1 0 1 5 3 2 4 4

Ответ равен [math]5[/math].

Альтернативный способ решения

Решим задачу, используя обход в ширину. Для этого заведем массив, в котором будем хранить веса кратчайших расстояний от начальной вершины до всех остальных. Совершая обход по графу, будем в каждой вершине для всех ее потомков проверять, уменьшится ли вес кратчайшего пути до сына, если пройти через текущую вершину. Если да, то весу кратчайшего расстояния до сына присваиваем значение, равное сумме веса кратчайшего расстояния до текущей вершины и стоимости прохода по ребру между вершиной и ее сыном. В силу особенности обхода графа, обновление весов кратчайших путей до сыновей вершины происходит только тогда, когда для нее уже найден оптимальный ответ.

См. также

Источники информации