如何求有向图中从节点A到节点B的道路条数？
我得到了一张图表，其中两个节点之间可以有多个拱形。
示例：
4 个节点 1→2 2→3 3->4 3->4 1->4
找出从节点 A 到节点 B 的道路条数的最佳方法是什么？
该示例的答案是 3 ： 1->2->3->4 ； 1->2->3->4 和 1->4
节点和拱门的限制是 1 000 000
我只考虑暴力算法。
还有其他想法吗？ 编辑：
图是非循环的
I'm given a graph which can have more than one arch between 2 nodes.
Example :
4 nodes
1->2
2->3
3->4
3->4
1->4
Which is the optim way to find the number of the roads from node A to node B ?
The answer for the example is 3 : 1->2->3->4 ; 1->2->3->4 and 1->4
Limit for nodes and archs are 1 000 000
I'm only thinking at a brute force algorithm.
Any other ideas?
Edit:
graph is acyclic
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果图形是循环的，那么结果是+无穷大，因为您可以根据需要多次循环运行。
一个可能适用于非循环有向图的想法：
尽管节点中的排序并不简单。但我确信您可以找到一种算法来解决这个问题，因为这是使用 DAG 时的常见问题。
If the graph is cyclic then the result is +infinity, since you can run in a cycle as often as you like.
One idea that might work on an acyclic directed graph:
Ordering in the nodes isn't trivial though. But I'm sure you can find an algorithm for that, since it's a common problem when using DAGs.
没有最佳的方法。该问题是一个NP完全问题。 http://en.wikipedia.org/wiki/Feedback_vertex_set
你只能找到好的解决方案
There is no optimal way. This Problem is a NP Complete problem. http://en.wikipedia.org/wiki/Feedback_vertex_set
You can only find good solutions