我想获得无向图中两个特定节点之间断开连接的最小权重。 图中的每个节点和边都有自己的权重。
可以通过多种不同方式删除一些权重来断开这两个节点的连接。 所以,我想获得断开连接时删除的权重的最小值。
在下面的示例中,我想要获得 Lidcombe 和 Redfern 之间断开连接的最小权重,结果为 2。 Example of graph
我尝试构建一个算法但失败了,所以我请求你的帮助。 谢谢。
最佳答案
https://web.williams.edu/Mathematics/sjmiller/public_html/hudson/Eusden_maxflowmincut.pdf从这个问题的一个很好的历史版本开始。冷战期间,研究出在 war 爆发时使东德与苏联分离的最有效方法。这里建议的答案是通过运行 Ford-Fulkerson 算法来使用最大流/最小割。您想要的断开连接由最小切割指定。
关于java - 求无向图中两个节点之间断开连接的最小权重,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58812246/