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

"Длина" пути - это количество ребер в пути.

Учитывая исходную и целевую вершину, я хочу найти количество путей из исходной вершины в целевую вершину заданной длины k.

  • Мы можем посещать каждую вершину столько раз, сколько хотим, поэтому, если путь от a до b будет выглядеть следующим образом: a -> c -> b -> c -> b считается действительным. Это означает, что могут быть циклы, и мы можем проходить через пункт назначения не один раз.

  • Две вершины могут быть соединены более чем одним ребром. Поэтому, если вершина a вершина b связана двумя ребрами, то пути, a -> b через ребро 1 и a -> b через ребро 2 считаются разными.

  • Число вершин N равно <= 70 и K, длина пути равна <= 10 ^ 9.

  • Поскольку ответ может быть очень большим, он должен сообщаться по модулю некоторого числа.

Вот что я думал до сих пор:

Мы можем использовать width-first-search без выделения каких-либо вершин в качестве посещенных, на каждой итерации мы отслеживаем количество ребер 'n_e', который мы требовали для этого пути, и product 'p' числа повторяющихся ребер, каждое ребро в нашем пути имеет.

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

Я думаю, что мы могли бы использовать поиск по глубине, а не по ширине первого поиска, так как нам не нужен кратчайший путь, а размер Q, используемый в широте первого поиска, может оказаться недостаточным.

Второй алгоритм, о котором я размышляю, что-то похожее на Алгоритм Флойда Варшалла, используя этот подход. Только нам не нужен кратчайший путь, поэтому я не уверен, что это правильно.

Проблема с моим первым алгоритмом заключается в том, что "K" может быть до 1000000000, и это означает, что мой поиск будет выполняться до тех пор, пока он не будет иметь 10 ^ 9 ребер, а n_e количество фронтов будет увеличено на 1 на каждом уровне, что будет очень медленным, и я не уверен, что он когда-либо закончится для больших ресурсов.

Поэтому мне нужен другой подход для решения этой проблемы; любая помощь будет принята с благодарностью.

Ответы

Ответ 1

Итак, вот замечательный трюк теории теории, который я помню для этого.

Сделайте матрицу смежности A. где A[i][j] равно 1, если есть ребро между i и j, а 0 в противном случае.

Тогда число путей длины k между i и j является просто записью [i][j] A ^ k.

Итак, чтобы решить проблему, постройте A и постройте A ^ k, используя матричное умножение (здесь применяется обычный трюк для выполнения возведения в степень). Затем просто найдите нужную запись.

EDIT: Ну, вам нужно сделать модульную арифметику внутри умножения матрицы, чтобы избежать проблем с переполнением, но это намного меньше.

Ответ 2

Собственно, запись [i] [j] в ^ k показывает общий различный "ход", а не "путь", в каждом простом графе. Мы можем легко доказать это "математической индукцией". Однако главный вопрос заключается в том, чтобы найти общий различный "путь" в заданном графе. У нас есть довольно много разных алгоритмов для решения, но верхняя полоса выглядит следующим образом:

(n-2) (n-3)... (n-k), который "k" - заданный параметр, указывающий длину пути.

Ответ 3

Позвольте мне добавить еще несколько материалов к вышеприведенным ответам (поскольку это расширенная проблема, с которой я столкнулся). Расширенная проблема -

Найдите количество путей длины k в заданном неориентированном дереве.

Решение для данной матрицы смежности A графа G простое. Выясните A k-1 и A k а затем подсчитайте число 1 в элементах над диагональю (или ниже).

Позвольте мне также добавить код python.

import numpy as np

def count_paths(v, n, a):
    # v: number of vertices, n: expected path length
    paths = 0    
    b = np.array(a, copy=True)

    for i in range(n-2):
        b = np.dot(b, a)

    c = np.dot(b, a)
    x = c - b

    for i in range(v):
        for j in range(i+1, v):
            if x[i][j] == 1:
                paths = paths + 1

    return paths

print count_paths(5, 2, np.array([
                np.array([0, 1, 0, 0, 0]),
                np.array([1, 0, 1, 0, 1]),
                np.array([0, 1, 0, 1, 0]),
                np.array([0, 0, 1, 0, 0]),
                np.array([0, 1, 0, 0, 0])
            ])