我目前正在根据R文档中找到的这段代码研究Ford-Fulkerson算法。
nodes <- 1:6
arcs <- matrix(c(1,2,1, 1,3,7, 2,3,1, 2,4,3, 2,5,2, 3,5,4, 4,5,1, 4,6,6,
5,6,2), byrow = TRUE, ncol = 3)
# Maximum flow with Ford-Fulkerson algorithm
maxFlowFordFulkerson(nodes, arcs, source.node = 2, sink.node = 6)
&amp; 得到了以下结果。
$`s.cut`
[1] 2 3 1 5
$t.cut
[1] 4 6
$max.flow
[1] 6
结果中说这个网络的最大流量是6。
但是,我一直试图用手计算最大流量&无论我怎么做,得到的最大流量都只有5。
&amp; 我能够得到的一些可能的流量。
2-->;4-->;5-->;6......【容量:1】。
2-->;5-->;4-->;6(倒流).[容量:1]
2->;5->;6..[能力:1]。
2->;4->;6...[能力:2]
[总容量:5]
或
2----gt;3----gt;5----gt;6......[能力:1]
2----gt;4----gt;5----gt;6......[能力:1]
2->;5->;4->;6(回流).[容量:1]
2->;4->;6..[能力:2]
[总容量:5]
我是不是理解错了流程?有谁能把最大流量6的路径一步步写下来?
我想你的说法是正确的(最大流量应该为 5
). 也许你可以试试 igraph
进行交叉检查,如。
df <- as.data.frame(`colnames<-`(arcs,c("from","to","capacity")))
g <- graph_from_data_frame(df)
res <- max_flow(g,2,6)
例如,得到
> res
$value
[1] 5
$flow
[1] 0 0 0 3 2 0 0 3 2
$cut
[1] 4 9
$partition1
+ 4/6 vertices, named, from bfc5f42:
[1] 1 2 3 5
$partition2
+ 2/6 vertices, named, from bfc5f42:
[1] 4 6
$stats
$stats$nopush
[1] 4
$stats$norelabel
[1] 3
$stats$nogap
[1] 2
$stats$nogapnodes
[1] 2
$stats$nobfs
[1] 1