加权有向无环图总流量算法

问题描述 投票:0回答:1

我正在研究一种算法,我想知道以下问题是否已被研究并有一个名称:

采用一个具有加权边和一个没有传入边的根节点的连通有向无环图。该根节点被分配初始流量值 1,该初始流量值作为连接子节点的边权重与父节点的流量值(1 为根)的乘积分配给其每个子节点。然后,每个节点的流量值都会分配给各自的子节点,依此类推,直到每个节点都有一个流量值,该值表示通过该节点的流量。

这个问题反映了一个物理系统,其中源头水以不同的比例分成不同的管道,其中管道可以再次重新组合,目标是计算固定的初始水量中有多少流过每个管道(节点)。在这种情况下,管道的容量是无限的,可以处理任意数量的水,因此只有初始分流比决定了来自父管道的水量。

我有一个算法来查找通过每个节点的流量,但我想知道这个问题是否存在并且有一个特定的名称,以便我可以查看是否遗漏了任何内容或使用了不正确的术语。

我找到了有关流网络的维基百科文章:https://en.wikipedia.org/wiki/Flow_network

但是,这个主题似乎针对的是每个管道内的流量受到限制的问题,并且流向其每个子管道的源的比例是一个需要优化的变量。对于我的问题,管道内的流量不受约束,但子管道之间的比率是预先确定的,目标是了解流向每个管道的流量。

algorithm graph-theory directed-acyclic-graphs
1个回答
0
投票

你有一棵树。

每条边的权重是 0 到 1 之间的数字,其中每个顶点的出边权重之和为 1。

通过任何给定边的流量是根顶点和边来源顶点之间所有边的权重的乘积。

© www.soinside.com 2019 - 2024. All rights reserved.