网络流程图中的节点阈值

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

是否存在一种流量网络扩展,允许人们在节点上设置阈值,并且仍然允许算法找到通过网络的最大流量?一个例子如下:

给定网络 S --> A --> T,其中 S 和 T 分别是源和宿。设a的阈值为3:如果流入A的流量小于3,则没有流量通过;否则,它的行为就像普通节点一样。在此示例中,如果 S-A 容量为 2,A-T 容量为 5,则最大流量将为 0。如果 S-A 容量为 5,A-T 容量为 5,则最大流量将为 5。

我尝试通过缓冲区节点重定向流量并使用下限,但我无法获得我所寻求的行为。

graph-theory max-flow network-flow ford-fulkerson
1个回答
0
投票
  • 将所有节点的阈值设置为 0(即所有节点都是“正常”)
  • 应用通常的算法
  • 循环节点
    • 如果通过节点的流量小于节点的阈值
      • 删除流经节点和节点
      • 在剩余节点上重新启动循环
  • 再次对没有删除节点的图应用通常的算法
© www.soinside.com 2019 - 2024. All rights reserved.