1

我得到了一个图表，它可以在 2 个节点之间有多个拱门。

例子 ：

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

我只考虑蛮力算法。

还有其他想法吗？编辑：

图是非循环的

4

2 回答 2

1

如果图形是循环的，则结果为 +infinity，因为您可以随意循环运行。

一个可能适用于无环有向图的想法：

  • 以某种方式对所有节点进行排序，以便对于任何两个连接的节点，父节点始终位于子节点之前
  • 将 0 分配给所有节点
  • 将 1 分配给起始节点
  • 从起始节点开始按该顺序迭代节点并执行
    • 如果节点是结束节点，你就完成了
    • 从这个节点开始的 Foreach 连接（即它是父节点）做
      • 将当前节点的值添加到子节点
  • 分配给结束节点的数字是您想要的结果

不过，在节点中排序并非易事。但我相信你可以找到一种算法，因为这是使用 DAG 时的常见问题。

于 2011-05-28T09:59:33.217 回答
0

没有最优的方法。这个问题是一个NP完全问题。http://en.wikipedia.org/wiki/Feedback_vertex_set

你只能找到好的解决方案

于 2011-05-28T10:00:54.823 回答