查找两个节点之间路径数的更快算法

Question

我想在Python回答一个在线评委的问题，但是我超过了时间限制和内存限制。这个问题几乎是在询问从起始节点到结束节点的所有路径的数量。可以看到完整的问题规范here.

这是我的代码：

import sys
lines = sys.stdin.read().strip().split('\n')
n = int(lines[0])
dict1 = {}

for i in xrange(1, n+1):
    dict1[i] = []

for i in xrange(1, len(lines) - 1):
    numbers = map(int, lines[i].split())
    num1 = numbers[0]
    num2 = numbers[1]
    dict1[num2].append(num1)

def pathfinder(start, graph, count):
    new = []
    if start == []:
        return count
    for i in start:
        numList = graph[i]
        for j in numList:
            if j == 1:
                count += 1
            else:
                new.append(j)

    return pathfinder(new, graph, count)   

print pathfinder([n], dict1, 0)

代码所做的是它从末端节点开始，并通过探索所有相邻节点向上移动到顶部。我基本上做了一个广度优先搜索算法，但是它占用了太多 space 和时间。我怎样才能改进这段代码以使其更有效率？是不是我的方法不对，我该如何解决？

Answer 1

你正在做的是那个代码中的 DFS（不是 BFS）...

这里有一个 link 好的解决方案... 编辑：请改用这种方法...

http://www.geeksforgeeks.org/find-paths-given-source-destination/

Answer 2

由于该图是非循环的，所以我们可以立即看出它是 1, 2, ..., n 的拓扑排序。所以我们可以像求解longest path problem一样使用动态规划。在列表 paths 中，元素 paths[i] 存储从 1 到 i 的路径数。更新很简单——对于每个边 (i,j)，其中 i 来自我们的拓扑顺序，我们执行 paths[j] += path[i]。

from collections import defaultdict

graph = defaultdict(list)
n = int(input())
while True:
    tokens = input().split()
    a, b = int(tokens[0]), int(tokens[1])
    if a == 0:
        break
    graph[a].append(b)

paths = [0] * (n+1)
paths[1] = 1
for i in range(1, n+1):
    for j in graph[i]:
        paths[j] += paths[i]
print(paths[n])

请注意，您正在实施的实际上并不是 BFS，因为您没有标记您访问过哪些顶点，这使得您的 start 增长不成比例。

测试图表

for i in range(1, n+1):
    dict1[i] = list(range(i-1, 0, -1))

如果你打印 start 的大小，你可以看到给定的 n 得到的最大值正好和 binomial(n, floor(n/2)) 一样增长，即 ~4^n/sqrt(n)。另请注意，BFS 不是您想要的，因为无法以这种方式计算路径数。

Answer 3

import sys
from collections import defaultdict

def build_matrix(filename, x):
    # A[i] stores number of paths from node x to node i.

    # O(n) to build parents_of_node
    parents_of_node = defaultdict(list)
    with open(filename) as infile:
        num_nodes = int(infile.readline())
        A = [0] * (num_nodes + 1)  # A[0] is dummy variable. Not used.
        for line in infile:
            if line == "0 0":
                break

            u, v = map(int, line.strip().split())
            parents_of_node[v].append(u)

            # Initialize all direct descendants of x to 1
            if u == x:
                A[v] = 1

    # Number of paths from x to i = sum(number of paths from x to parent of i)
    for i in xrange(1, num_nodes + 1):  # O(n)
        A[i] += sum(A[p] for p in parents_of_node[i])  # O(max fan-in of graph), assuming O(1) for accessing dict.

    # Total time complexity to build A is O(n * (max_fan-in of graph))
    return A


def main():
    filename = sys.argv[1]

    x = 1  # Find number of paths from x
    y = 4  # to y

    A = build_matrix(filename, x)
    print(A[y])

查找两个节点之间路径数的更快算法

Faster algorithm for finding number of paths between two nodes

python

algorithm

graph-theory

nodes

python-2.7