带权根节点有向无环图节点流量计算问题的名称问询
带权有向无环图的比例流量分配问题命名确认
我正在研究一种算法,想确认下述问题是否已被研究并存在特定名称:
问题核心定义
- 给定带权边的连通有向无环图(DAG),存在一个无入边的根节点,初始流量值设为1
- 根节点的流量按边权比例分配给子节点:子节点流量 = 父节点流量 × 对应边权
- 后续节点依次按此规则完成分流与汇流,最终所有节点获得代表流经自身的流量值
- 场景类比:类似物理系统中源头水流按比例分流、汇流,管道无容量限制,仅由分流比例决定流量
补充说明
- 我已经有计算节点流量的算法,但需要确认该问题的特定名称,避免术语误用或遗漏关键研究要点
- 查阅过流网络(Flow Network)相关内容,但该主题聚焦带容量限制的流量优化问题,与本问题(无流量限制、边权比例固定、目标为计算各节点流量)不符
- 该问题不限于树结构,适用于所有带根节点的有向无环图
示例计算
初始节点A流量为1,边标签为父节点流向子节点的流量比例,计算结果如下:
- A = 1
- B = 0.4 × A = 0.4
- C = 0.4 × A + 0.5 × B = 0.6
- D = 0.2 × A = 0.2
- E = C + D = 0.8
- F = 0.5 × B = 0.2
内容的提问来源于stack exchange,提问作者Forwood Cloud Wiser
相关产品推荐
相关产品推荐

