我正在寻找一种算法来计算通过 DAG 中特定节点的路径数(类似于“介数”的概念),具有以下条件和约束:
我需要对图中的一组源/目标节点进行计数,而不是所有节点,即对于中间节点 n,我想知道从节点集 S 到节点集 D 有多少条不同的最短路径通过通过 n (并且通过不同,我的意思是每两条路径至少有一个非公共节点)
考虑到 DAG 可能非常大但边缘稀疏,因此您可能建议使用哪些算法来执行此操作,因此不优先考虑节点上的深层嵌套循环。
我正在寻找一种算法来计算通过 DAG 中特定节点的路径数(类似于“介数”的概念),具有以下条件和约束:
我需要对图中的一组源/目标节点进行计数,而不是所有节点,即对于中间节点 n,我想知道从节点集 S 到节点集 D 有多少条不同的最短路径通过通过 n (并且通过不同,我的意思是每两条路径至少有一个非公共节点)
考虑到 DAG 可能非常大但边缘稀疏,因此您可能建议使用哪些算法来执行此操作,因此不优先考虑节点上的深层嵌套循环。