use*_*368 6 algorithm graph path count directed-acyclic-graphs
我正在寻找一种算法来计算穿过DAG中特定节点的路径数量(类似于"中介性"的概念),具有以下条件和约束:
我需要对图中的一组源/目标节点进行计数,而不是所有节点,即对于中间节点n,我想知道从节点集S到节点集D通过多少条不同的最短路径通过n(和不同的,我的意思是每两个路径至少有一个非公共节点)
考虑到DAG可能非常大但边缘稀疏,因此您可能建议使用哪些算法,因此不会优先考虑节点上的深嵌套循环.
您可以对每对 Src/Dest 节点使用广度优先搜索，并查看其中哪些节点在路径中具有您的给定节点。您必须稍微修改搜索，以便在找到最短路径后，继续清空队列，直到到达导致增加大小的路径。这样，如果存在多个最短路径，您就不会受到随机机会的约束。当然，这只是非加权图表的一个选项。