Алгоритм подсчета количества путей из одной вершины направленного графа в другую

[Resha]

Алгоритм подсчета количества путей из одной вершины направленного графа в другую

Здравствуйте.

Есть таблица связности вершин ациклического ориентированного графа, любая вершина которого, кроме корневой, имеет хотя бы одного родителя (но может иметь и нескольких родителей):
parent_id INT - идентификатор вершины, из которой начинается путь
child_id INT - идентификатор вершины в которой заканчивается путь
path_count INT - количество путей из вершины parent_id в вершины child_id

Пытаюсь найти алгоритмы пересчета path_count при:
1. Создании ребра между двумя вершинами графа
2. Удалении ребра между двумя вершинами графа

Подскажите, может быть есть какой-то алгоритм для подсчета количества путей между двумя вершинами?

 

[Alexandre]

гугли по слову Динамическое программирование/графы
классический алгоритм
море информации по "определению оптимального пути"

 

[Resha]

Определение оптимального пути мне как раз не нужно:
1. у ребер в моем графе нет веса;
2. мне важно именно количество путей из одного узла в другое, сам маршрут мне не важен.

При этом, хотелось бы отталкиваться от уже посчитанного количества путей, а не производить полный пересчет. Все никак не могу вывести закон, каким образом суммировать/перемножать количество путей при создании ребра между двумя подграфами.

 

[rotoZOOM]

С большой долей вероятности алгоритм такой:
строим полный ориентированный взвешанный граф.
Вес каждого ребра определяем следующим образом: вес (u,v) = если в исходном графе существует ребро (u,v), то 1, иначе 0.
Далее запускаем на этом графе слегка переработанный алгоритм Флойда:

for ($i = 0; $i < кол-во вершин; $i++)
{
    for ($j = 0; $j < кол-во вершин; $j++)
    {
        for ($k = 0; $k < кол-во вершин; $k++)
        {
               вес_ребра ($j,$k) += min (вес_ребра($j,$i),вес_ребра($i,$k));
        }
    }
}

после окончания цикла соответсвенно вес ребра (u,v) = количеству путей от u до v.
Сложность алгороитма O(N^3), где N - кол-во вершин.
Это если пересчитывать весь граф.

Если же нужно найти кол-во путей от одной вершины до другой, то можно использовать волновой алгоритм (очередь).

 

[Resha]

Алгоритм уже нашелся.

Например, при построении ребра, связывающего вершину P (parent) с вершиной C (child):
Находим все вершины, из которых есть путь в P, (родителей P) и все вершины, в которые есть путь из C, (потомков C) в этой же таблице связности.

Количество путей из Pi (один из родителей P) в Cj (один из потомков C):
newCount = сount(Pi, Cj) + count(Pi, P) * count(C, Cj), где count(Pi, Cj) - прежнее количество путей (если вершины до этого не были связаны, равно 0), count(C, Cj) - количество путей между C и Cj, count(Pi, P) - количество путей между Pi и P.

Очень удобно в этом случае всегда иметь линк count(N, N) = 1, где N - вершина графа, для всех вершин (т.е. мнимое ребро для связи с собой). Это помогает упростить построение таблицы связности - непосредственно связываемые вершины (C и P) будут включены в родителей P и потомков C и описанный алгоритм к их связи тоже применим.

Вот код:

    public function add($node, $parent)
    {
        $parentParents = $this->getParents($parent);
        foreach ($parentParents as $parentParent) {
            $count = $this->getCount($parentParent, $parent);
            $this->createPathCount($parentParent, $node, $count);
        }
        $this->createPathCount($parent, $node, 1);
        return $this;
    }
    
    public function append($node, $parent)
    {
        $parentParents = $this->getParents($parent);
        $childChildren = $this->getChildren($node);
        foreach ($parentParents as $parentParent) {
            foreach ($childChildren as $childChild) {
                $parentCount = $this->getCount($parentParent, $parent);
                $childCount = $this->getCount($node, $childChild);
                $count = $parentCount * $childCount;
                $oldCount = $this->getCount($parentParent, $childChild);
                if (!$oldCount) {
                    $this->createPathCount($parentParent, $childChild, $count);
                } else {
                    $this->updatePathCount($parentParent, $childChild, $count);
                }
            }
        }
    }

Код не оптимизирован (в любом случае, все будет закинуто в хранимую процедуру в БД) и с точки ООП достаточно бессмысленен Но смысл алгоритма должен быть понятен. Удаление ребра делается по аналогии, только меняем "+" на "-", время от времени чистим строки, где path_count = 0.