英文:
Find the number of simple paths from A to B going through a given point on the graph
问题
我正在研究网络中的一个有趣问题。
给定一个可能包含循环的无向图：
我选择两个点，A和B作为路径的起点和终点。我的目标是计算通过图中每个其他节点的简单路径有多少个。
例如，在这个图中：
从0到4有4条简单路径。节点3有4个计数，节点1和2有2个计数。
暴力解决这个问题是不可能的，因为它需要找到所有简单路径，其复杂度是O(n!)的数量级。
我尝试修改Floyd-Warshall算法，但我找不到一个好的递归公式 - 我只能计算所有路径，而不仅仅是简单路径。
有没有在多项式时间内解决这个问题的解决方案？
谢谢！
英文:
I am looking into an interesting issue in networks.
Given an undirected graph which can contain cycles:
I choose two points, A and B as origin and end of my paths. My goal is to calculate how many simple paths go through each of the other nodes in the graph.
For example, in this graph:
there are 4 simple paths from 0 to 4. Node 3 has a count of 4, nodes 1 and 2 have a count of 2.
Brute forcing this is impossible, since it would require finding all simple paths, which is on the order of O(n!).
I tried to make a variation of the Floyd–Warshall algorithm, but I cannot find a good recursive formula - I can only manage to count all paths, not only simple ones.
Is there a solution to this problem in polynomial time?
Thank you!
答案1
得分: 1
据所有人所知，对于这个问题，没有一个多项式时间的算法。在一个图中计算从s到t的简单路径的数量 - 即使只是计算它们的数量，而不是列举它们 - 这是一个#P-complete问题。由于对于一个#P-complete问题的多项式时间算法将证明P = NP，因此目前没有已知的多项式时间算法来解决这个问题。
英文:
To the best anyone knows, no, there isn’t a polynomial-time algorithm for this problem. The problem of counting how many s-t simple paths there are in a graph - not even listing them, just counting them - is #P-complete. Since a polynomial-time algorithm for a #P-complete problem would prove P = NP, there are no known polynomial-time algorithms for this problem.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论