algorithm - 计算通过 DAG 中节点的最短路径数

Question

我正在寻找一种算法来计算穿过 DAG 中特定节点的路径数(类似于“中间性”的概念)，具有以下条件和约束:

我需要计算图中的一组源/目标节点，而不是所有节点，即对于中间节点 n，我想知道从节点集 S 到节点集节点 D 通过 n(并且不同，我的意思是每两条路径至少有一个非公共(public)节点)

考虑到 DAG 可能非常大但边缘稀疏，因此您可能会建议执行此操作的算法是什么，因此不优先考虑节点上的深层嵌套循环。

Answer 1

您可以对每对 Src/Dest 节点使用广度优先搜索，并查看其中哪些节点在路径中有您给定的节点。您将不得不稍微修改搜索，以便一旦找到最短路径，就继续清空队列，直到到达导致您增加大小的路径。这样，如果有多个最短路径，您就不会受到随机机会的约束。当然，这只是非加权图的一个选项。