如何计算有向无环图中通过一个节点的最短路径数量？

Question

6

我正在寻找一种算法，用于计算DAG中穿过特定节点的路径数量（类似于“Betweenness”的概念），具备以下条件和限制：

我需要对图中一组源/目标节点进行计数，而不是所有节点。即对于一个中间节点n，我想知道从节点集合S到节点集合D有多少个经过n的不同最短路径（通过不同，我的意思是每两条路径至少有一个非共同节点）。

考虑到DAG可能非常大但稀疏，因此不建议采用深度嵌套循环节点的方式，您可以提供哪些算法来完成此任务？

- user622368

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- corsiKa · Accepted Answer

您可以对每个Src/Dest节点对使用广度优先搜索，查看哪些路径中包含了给定的节点。您需要略微修改搜索算法，以便在找到最短路径后，继续清空队列，直到找到会导致增加路径长度的路径。这样，即使有多条最短路径，您也不会受到随机因素的影响。当然，这仅适用于非加权图。