Add test for two-phase shortest augmenting path maxflow algorithm

2 files changed, 14 insertions, 1 deletions

diff --git a/networkx/algorithms/flow/shortest_augmenting_path.py b/networkx/algorithms/flow/shortest_augmenting_path.py
index 889075fe..152486a4 100644
--- a/networkx/algorithms/flow/shortest_augmenting_path.py
+++ b/networkx/algorithms/flow/shortest_augmenting_path.py
@@ -89,7 +89,7 @@ def shortest_augmenting_path_impl(G, s, t, capacity, two_phase):
     path = [s]
     u = s
     d = n if not two_phase else int(min(m ** 0.5, 2 * n ** (2. / 3)))
-    done = R.node[s]['height'] < d
+    done = R.node[s]['height'] >= d
     while not done:
         height = R.node[u]['height']
         curr_edge = R.node[u]['curr_edge']
diff --git a/networkx/algorithms/flow/tests/test_maxflow.py b/networkx/algorithms/flow/tests/test_maxflow.py
index 0053aca7..3994d679 100644
--- a/networkx/algorithms/flow/tests/test_maxflow.py
+++ b/networkx/algorithms/flow/tests/test_maxflow.py
@@ -322,3 +322,16 @@ class TestMaxflow:
         assert_equal(nx.preflow_push(G, 1, 2, global_relabel_freq=None)[0], 1)
         assert_raises(nx.NetworkXError, nx.preflow_push_value, G, 1, 2,
                       global_relabel_freq=-1)
+
+    def test_shortest_augmenting_path_two_phase(self):
+        k = 5
+        p = 1000
+        G = nx.DiGraph()
+        for i in range(k):
+            G.add_edge('s', (i, 0), capacity=1)
+            G.add_path(((i, j) for j in range(p)), capacity=1)
+            G.add_edge((i, p - 1), 't', capacity=1)
+        assert_equal(nx.shortest_augmenting_path_value(
+            G, 's', 't', two_phase=True), k)
+        assert_equal(nx.shortest_augmenting_path_value(
+            G, 's', 't', two_phase=False), k)