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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
Пусть дан ациклический ориентированный взвешенный граф. Требуется найти вес кратчайшего пути из '''u''' в '''v'''
+
{{Задача
{{Определение|definition= '''Кратчайший путь''' из вершины '''u''' в вершину '''v''' – это такой путь из вершины '''u '''в вершину '''v''', что его суммарный вес входящих в него ребер минимален}}
+
|definition =
 +
Пусть дан [[Основные_определения_теории_графов |ациклический ориентированный взвешенный граф]]. Требуется найти вес кратчайшего пути из <tex>u</tex> в <tex>v</tex>.
 +
}}
 +
{{Определение|definition= '''Кратчайший путь''' из вершины '''u''' в вершину '''v''' – это такой путь из вершины '''u '''в вершину '''v''', что суммарный вес входящих в него ребер минимален.}}
 
==Решение==
 
==Решение==
Пусть <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</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>
 
: <tex> d(i) = \min\limits_{\mathop{j:j \rightsquigarrow i}} (d(j) + w(j, i)) </tex>
  
Строка 13: Строка 16:
 
   <font color=green>//p {{---}} массив индексов вершин графа в порядке топологической сортировки</font>
 
   <font color=green>//p {{---}} массив индексов вершин графа в порядке топологической сортировки</font>
 
   '''for''' i = 1 .. n
 
   '''for''' i = 1 .. n
     d[i] = '''infinity'''
+
     d[i] = <tex>\infty</tex>
 
   d[u] = 0 <font color=green>// где u {{---}} начальная вершина</font><br />
 
   d[u] = 0 <font color=green>// где u {{---}} начальная вершина</font><br />
 
   p = topSort(w) <font color=green>//топологическая сортировка графа</font>
 
   p = topSort(w) <font color=green>//топологическая сортировка графа</font>
Строка 22: Строка 25:
 
==Пример==
 
==Пример==
 
[[Файл:WayAcyclicGraph.png|thumb|right|500px|Граф из примера]]
 
[[Файл: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;"
 
|-
 
|-
Строка 43: Строка 46:
 
| '''8''' ||  -  ||  -  ||  -  ||  1  ||  -  ||  -  ||  -  ||  -  
 
| '''8''' ||  -  ||  -  ||  -  ||  1  ||  -  ||  -  ||  -  ||  -  
 
|}
 
|}
Требуется найти путь из '''2''' в '''4'''. <br />
+
Требуется найти вес кратчайшего пути из '''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''' || '''5''' || '''6''' || '''7''' || '''8'''
+
| <tex>i</tex> || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''
 
|-
 
|-
| 2 || 3 || 6 || 7 || 1 || 5 || 8 || 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''' || '''5''' || '''6''' || '''7''' || '''8'''
+
| <tex>i</tex> || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''
 
|-
 
|-
| 1 || 0 || 1 || 5 || 3 || 2 || 4 || 4
+
| <tex>d[i]</tex> || 1 || 0 || 1 || 5 || 3 || 2 || 4 || 4
 
|}
 
|}
  
Ответ равен 5.
+
Ответ равен <tex>5</tex>.
  
 
==Альтернативный способ решения==
 
==Альтернативный способ решения==
Задачу так же можно решить [[Обход_в_ширину |поиском в ширину]]. Для этого будем поддерживать массив кратчайший расстояний от начальной до текущей вершины. Обходя граф в ширину, будем для каждой вершины обновлять ответы у ее сыновей как минимум из старого значения и пути, проходящего через текущую вершину.
+
Решим задачу, используя [[Обход_в_ширину |обход в ширину]]. Для этого заведем массив, в котором будем хранить веса кратчайших расстояний от начальной вершины до всех остальных. Совершая обход по графу, будем в каждой вершине для всех ее потомков проверять, уменьшится ли вес кратчайшего пути до сына, если пройти через текущую вершину. Если да, то весу кратчайшего расстояния до сына присваиваем значение, равное сумме веса кратчайшего расстояния до текущей вершины и стоимости прохода по ребру между вершиной и ее сыном.
 +
В силу особенности обхода графа, обновление весов кратчайших путей до сыновей вершины происходит только тогда, когда для нее уже найден оптимальный ответ.
  
В силу особенности обхода графа, когда происходит обновление сыновей вершины, для нее самой уже найден оптимальный ответ.
+
==См. также==
 
 
==Смотри также==
 
*[[Обход_в_ширину | Обход в ширину]]
 
 
*[[Алгоритм_Флойда_—_Уоршалла |Алгоритм Флойда—Уоршалла]]
 
*[[Алгоритм_Флойда_—_Уоршалла |Алгоритм Флойда—Уоршалла]]
 
*[[Алгоритм_Дейкстры |Алгоритм Дейкстры]]
 
*[[Алгоритм_Дейкстры |Алгоритм Дейкстры]]

Версия 21:32, 15 декабря 2014

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


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

Решение

Пусть [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 - - - 5 - - - -
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].

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

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

См. также

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