Как найти все простые пути длиной не более k, начинающиеся в вершине ориентированного графа?

Для этого вы должны использовать обход в глубину. Рекурсивная функция является естественным выбором для этого. Он возвращался на глубину k и затем воспроизводил путь, который прошел. При каждом рекурсивном вызове убедитесь, что вы не добавляете узел к пути, который уже находится на пути. И когда вы выходите из рекурсивного вызова, соответственно сократите путь.

Вот реализация на JavaScript, где рекурсивная функция принимает в качестве аргумента список смежности (для представления графа), текущий узел, значение k и путь в виде набора (упорядоченный хэш-набор).

function* genPaths(adj, node, k, path=new Set) {
    if (path.has(node)) return; // cycle detected!
    if (k == 0) return yield [...path, node]; // We have a result
    path.add(node);
    for (const neighbor of adj[node]) {
        yield* genPaths(adj, neighbor, k - 1, path);
    }
    path.delete(node); // backtrack
}

// Demo
const adj = {
    "1": ["2", "3"],
    "2": [],
    "3": ["2", "4"],
    "4": ["3"]
};

// Finding paths with k=1, k=2 and k=3:
for (let k = 1; k <= 3; k++) {
    console.info("results for k  = ", k);
    for (const path of genPaths(adj, "1", k)) {
        console.info("  ", ...path);
    }
}
console.info("done");

Продлить его...

Вышеупомянутая функция возвращает пути ровно k длины, и основной код использует ее для получения путей нескольких разных длин. Если вас всегда интересуют все более короткие пути, даже включая путь с размером 0 (только начальный узел), вы можете расширить функцию, чтобы сделать все это с помощью одного вызова верхнего уровня:

function* genPaths(adj, node, k, path=new Set) {
    if (path.has(node)) return; // cycle detected!
    yield [...path, node]; // We have a result (0 <= path size <= k)
    if (k == 0) return;
    path.add(node);
    for (const neighbor of adj[node]) {
        yield* genPaths(adj, neighbor, k - 1, path);
    }
    path.delete(node); // backtrack
}

// Demo
const adj = {
    "1": ["2", "3"],
    "2": [],
    "3": ["2", "4"],
    "4": ["3"]
};

// Finding paths with size <= 3:
for (const path of genPaths(adj, "1", 3)) {
    console.info("  ", ...path);
}
console.info("done");

Обратите внимание, что размер пути выражается количеством ребер на нем, поэтому [1] — это путь длиной 0, [1, 3] — это путь длиной 1 и т. д.

Если вы хотите исключить путь длиной 0, просто добавьте условие в оператор yield:

    if (path.length > 0) yield [...path, node];

Вот псевдокод алгоритма Йена

IMPORT graph, source and sink
CLEAR vShortestPaths
calculate shortest path from source to sink, add to vShortestPaths
WHILE TRUE
   CLEAR vPotentialPaths
   SET work = graph
   LOOP PF over vShortestPaths
       LOOP spur over PF
            REMOVE out edge from spur in work used by PF
            calculate spurPath, shortest path from spur to sink in work
            IF spurPath exists
                CONTINUE to next iteration of LOOP spur
            SET newPath to combination of source to spur in PF and spurPath
            IF newPath NOT in vShortestPaths
                ADD newPath to vPotentialPaths
            END LOOP spur
        END LOOP PF
    IF vPotentialPaths NOT empty
        ADD shortest path in vPotentialPaths to vShortestPaths
    END WHILE TRUE 

Чтобы найти все пути в графе:

Set vertices into fixed order ( input order is fine )
LOOP I over vertices
   LOOP J over the (J+1)the to the last vertex
       Apply Yen to I,J vertex pair

Версия обхода DFS с возвратом^*, используемая Goodrich, Tamassia & Goldwasser (2013) в разделах 14.3.1–14.3.2, может быть изменена и адаптирована для решения этой проблемы.

Мы также хотим отслеживать посещенные вершины и соответствующие ребра дерева (или ребра открытия) с помощью упорядоченной хэш-таблицы (что подразумевает, что ваша вершина должна быть хешируемой), что предотвращает циклический обход (с помощью карты смежности для представления Graph, мы можем запросить пройденные вершины за время O (1) и опустить задние ребра).

В конечном итоге это приведет к созданию (подразумеваемых) сильно связных компонентов (или связных компонентов в случае неориентированного графа), достижимых путем обхода не более k-1 ребер в графе путем вызова DFS в начальной вершине s. , а затем рекурсивно вызывая DFS для всех случайных вершин обнаружения в указанном k-диапазоне.

_{* We populate a concurrent path accumulator for every valid recursive DFS call (when traversed edges < k) , and then backtrack and pop the corresponding retraction edges (triggered when traversed edges >= k, until a new edge is traversed and accumulated again) as the recursion unwinds.}

В следующем решении используется представление графика на карте смежности, представленное Goodrich et al. (стр. 635-637). Для краткости, реализацию Graph, которая на 100% совместима с этим алгоритмом с нулевыми зависимостями, можно найти здесь: graph.py .

Все методы Graph.insert_vertex(), Graph.insert_edge(), Edge.opposite(), Edge.endpoints() выполняются за время O(1), за исключением Graph.incident_edges(v), который занимает время O(исходящая степень(v)).

Первоначально klen_dfs() должно занимать время O(n) в худшем случае (когда для поиска вершины, достижимой в k ребрах, требуется обход всего графа). Однако сохранение каждого уникального пути (с помощью строки path_array.append(p[:])) вызывает некоторые необходимые повторные вычисления, накапливающие приблизительно операции суммирования (k) для каждого пройденного пути длины k, то есть n_k × суммирование (k), где n_k - количество вершин достижима, пройдя k ребер. В целом, klen_dfs() в худшем случае занимает O((n_k× k²) + n) времени.

from collections import OrderedDict
from typing import List
from graph import Graph


def init_graph():
    G = Graph(directed=True)

    v1 = G.insert_vertex(1)
    v2 = G.insert_vertex(2)
    v3 = G.insert_vertex(3)
    v4 = G.insert_vertex(4)

    G.insert_edge(v1, v2)
    G.insert_edge(v1, v3)
    G.insert_edge(v3, v2)
    G.insert_edge(v3, v4)
    G.insert_edge(v4, v3)

    return G, v1


def klen_dfs(G: Graph, s: Graph.Vertex, k: int):
    """Report all paths (edge lists) less than length k.
    G - Adjacency Map Graph ADT
    s - Starting vertex
    k - Path length limit (actual limit = k-1)
    """
    discovery_edges: OrderedDict[Graph.Vertex, Graph.Edge] = OrderedDict()
    path_accummulator: List[Graph.Edge] = [ ]
    path_array: List[List[Graph.Edge]] = [ ]

    def dfs(g: Graph, u: Graph.Vertex, discovered, klen, p):
        """Traditional DFS with addtional params.
        u - A vertex in G
        p - Concurrent path array of less than k edges
        """
        if klen < k:
            for e in g.incident_edges(u, outgoing=True):
                v = e.opposite(u)
                if not discovered.get(v):   # Cyclic traversal prevention
                    discovered[v] = e
                    p.append(e)
                    path_array.append(p[:])
                    dfs(g, v, discovered, klen + 1, p)
                    p.pop()
                    discovered.pop(v)

    dfs(G, s, discovery_edges, 1, path_accummulator)
    return path_array


if __name__ == "__main__":
    # For graph produced by init_graph(), all k >= 3 has same results
    for K in range(1,4):
        digraph, start = init_graph()
        paths = klen_dfs(digraph, start, K)
        formatted_paths = []
        for path in paths:
            formatted_path = []
            for edge in path:
                endpoints = edge.endpoints()
                formatted_path.append((
                    endpoints[0].element(), endpoints[1].element()))
            formatted_paths.append(formatted_path)
        print(f"ALL paths when k = {K} (i.e of length {K-1} < k length)")
        print(*formatted_paths, sep = "\n")
        print()

Выход:

ALL paths when k = 1 (i.e of length 0 < k length)

ALL paths when k = 2 (i.e of length 1 < k length)
[(1, 2)]
[(1, 3)]

ALL paths when k = 3 (i.e of length 2 < k length)
[(1, 2)]
[(1, 3)]
[(1, 3), (3, 2)]
[(1, 3), (3, 4)]

Визуализация простых допустимых путей длиной меньше k=3 при s=1

Другие соображения: пути строго k-длины.

После изменений в ответе Тринкота в противном случае мы можем выбрать сообщать только те пути, длина которых имеет размер k, заменив строку во вложенной функции dfs(): path_array.append(p[:]) на if klen == k-1: path_array.append(p[:]).

Это уменьшает временную сложность с O((n_k× k²) + n) до O((n_k× k) + n) и дает следующий результат:

ALL paths when k = 1 (i.e of length 0 < k length)

ALL paths when k = 2 (i.e of length 1 < k length)
[(1, 2)]
[(1, 3)]

ALL paths when k = 3 (i.e of length 2 < k length)
[(1, 3), (3, 2)]
[(1, 3), (3, 4)]