26
правок
Изменения
Нет описания правки
'''else'''
sum = 0
'''for'''(всех <tex>c</tex> смежных с <tex>v</tex>):
sum += '''count'''(c)
d[v] = sum
'''return''' sum
'''countPaths'''(s, t):
d[s] = 1
w[s] = true
[[Файл: count-path-graph-example.png|thumb|300px| description ]]
Изначально массивы <tex>d</tex> и <tex>w</tex> инициализированы следующим образом:
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| '''вершина''' || S || 1 || 2 || 3 || 4 || T
|-
| '''w''' || true || false || false || false || false || false
|-
| '''d''' || 1 || 0 || 0 || 0 || 0 || 0
|}
Сначала функция <tex>count</tex> будет вызвана от вершины <tex>T</tex>. Ответ для нее еще не посчитан (<tex>w[T] = false</tex>), следовательно <tex>count</tex> будет вызвана от вершин <tex>3</tex> и <tex>4</tex>. Для вершины <tex>3</tex> ответ также не посчитан (<tex>w[3] = false</tex>), следовательно <tex>count</tex> будет вызвана уже для вершин <tex>2</tex> и <tex>S</tex>. А вот для них ответ мы уже можем узнать: для <tex>2</tex> он равен <tex>d[S]</tex>, так как это <tex>S</tex> - единствнная вершина, ребро из которой входит в нее. Непосредственно для <tex>S</tex> ответ нам также известен. На текущий момент таблица будет выглядеть следующим образом:
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| '''вершина''' || S || 1 || 2 || 3 || 4 || T
|-
| '''w''' || true || false || '''true''' || false || false || false
|-
| '''d''' || 1 || 0 || '''1''' || 0 || 0 || 0
|}
Теперь мы знаем значения для вершин <tex>2</tex> и <tex>S</tex>, что позволяет вычислить <tex>d[3] = d[2] + d[S] = 2</tex>. Также обновим значения в массиве <tex>w</tex>: <tex>w[3] = true</tex>.
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| '''вершина''' || S || 1 || 2 || 3 || 4 || T
|-
| '''w''' || true || false || true || '''true''' || false || false
|-
| '''d''' || 1 || 0 || 1 || '''2''' || 0 || 0
|}
В самом начале для вычисления <tex>d[T]</tex> нам требовались значения <tex>d[3]</tex> и <tex>d[4]</tex>. Теперь нам известно значение <tex>d[3]</tex>, поэтому проследим за тем, как будет вычисляться <tex>d[4]</tex>. <tex>d[4] = count(3) + count(2) + count(1)</tex>, но <tex>w[3] = true, w[2] = true</tex>, следовательно значения <tex>d[3]</tex> и <tex>d[2]</tex> мы уже знаем, и нам необходимо вызвать <tex>count(1)</tex>. Ответ для этой вершины равен <tex>d[S]</tex>, так как это единственная вершина, ребро из которой входит в <tex>1</tex>. Обновим соответствующие значения массивов <tex>d</tex> и <tex>w</tex>:
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| '''вершина''' || S || 1 || 2 || 3 || 4 || T
|-
| '''w''' || true || '''true''' || true || true || false || false
|-
| '''d''' || 1 || '''1''' || 1 || 2 || 0 || 0
|}
Теперь нам известны все три значения, требующиеся для вычисления ответа для вершины <tex>4</tex>. <tex>d[4] = d[3] + d[2] + d[1] = 2 + 1 + 1 = 4</tex>:
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| '''вершина''' || S || 1 || 2 || 3 || 4 || T
|-
| '''w''' || true || true || true || true || '''true''' || false
|-
| '''d''' || 1 || 1 || 1 || 2 || '''4''' || 0
|}
Наконец, вычислим <tex>d[T] = d[3] + d[4] = 2 + 4 = 6</tex> и обновим таблицы <tex>d</tex> и<tex>w</tex>:
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| '''вершина''' || S || 1 || 2 || 3 || 4 || T
|-
| '''w''' || true || true || true || true || true || '''true'''
|-
| '''d''' || 1 || 1 || 1 || 2 || 4 || '''6'''
|}
Этот алгоритм позволяет вычислить количество путей от какой-либо вершины <tex>S</tex> не только до <tex>T</tex>, но и для любой вершины, лежащей на любом из путей от <tex>S</tex> до <tex>T</tex>. Для этого достаточно взять значение в соответствующей ячейке <tex>d</tex>.
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
