我有一个N x M矩阵,我有一定数量的源和汇,我需要找到它们之间不相交的最大路径,基本上两条路径不能使用相同的顶点。为了确保这一点,我已经将所有顶点的所有最大容量设置为1。我已经尝试将BFS算法与Ford-Fulkerson算法相结合,使用连接到所有源的超源和由所有汇点连接的超链,但它并不总是返回正确数量的最大路径。
但是,我需要在运行时间为|V| x |E|的有向图中找到顶点不相交路径的最大数量K。我知道将每个顶点转换为v_in,v_out,然后从v_in到v_out添加容量为1的边,并为每一对顶点(u,v)添加容量为1的边从u_out到v_in的算法,然后计算此网络中的最大流量。然而,在我的计算之后,这个算法对于最大流量需要O(E)预处理+ O(VE^2)或O(V^2E)。我做错了什么吗?