diff --git a/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java
index cf35f66..91204fc 100644
--- a/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/AbstractGraphPathSearchTest.java
@@ -36,19 +36,19 @@
     public void noSuchSourceArgument() {
         graphSearch().search(new AdjacencyListsGraph<>(of(B, C),
                                                        of(new TestEdge(B, C, 1))),
-                             A, H, weight);
+                             A, H, weight, 1);
     }
 
     @Test(expected = NullPointerException.class)
     public void nullGraphArgument() {
-        graphSearch().search(null, A, H, weight);
+        graphSearch().search(null, A, H, weight, 1);
     }
 
     @Test(expected = NullPointerException.class)
     public void nullSourceArgument() {
         graphSearch().search(new AdjacencyListsGraph<>(of(B, C),
                                                        of(new TestEdge(B, C, 1))),
-                             null, H, weight);
+                             null, H, weight, 1);
     }
 
     @Test
diff --git a/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
index 4e9f5e6..9380054 100644
--- a/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
@@ -21,6 +21,7 @@
 import java.util.Set;
 
 import static org.junit.Assert.assertEquals;
+import static org.onlab.graph.GraphPathSearch.ALL_PATHS;
 
 /**
  * Test of the Bellman-Ford algorithm.
@@ -56,7 +57,7 @@
         graph = new AdjacencyListsGraph<>(vertexes, edges);
 
         GraphPathSearch<TestVertex, TestEdge> search = graphSearch();
-        Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, H, weight).paths();
+        Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, H, weight, ALL_PATHS).paths();
         assertEquals("incorrect paths count", 1, paths.size());
 
         Path p = paths.iterator().next();
@@ -65,10 +66,10 @@
         assertEquals("incorrect path length", 5, p.edges().size());
         assertEquals("incorrect path cost", 5.0, p.cost(), 0.1);
 
-        paths = search.search(graph, A, G, weight).paths();
+        paths = search.search(graph, A, G, weight, ALL_PATHS).paths();
         assertEquals("incorrect paths count", 0, paths.size());
 
-        paths = search.search(graph, A, null, weight).paths();
+        paths = search.search(graph, A, null, weight, ALL_PATHS).paths();
         printPaths(paths);
         assertEquals("incorrect paths count", 6, paths.size());
     }
diff --git a/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
index 96a77e6..76c0cc2 100644
--- a/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/BreadthFirstSearchTest.java
@@ -20,6 +20,7 @@
 import java.util.Set;
 
 import static org.junit.Assert.assertEquals;
+import static org.onlab.graph.GraphPathSearch.ALL_PATHS;
 
 /**
  * Test of the BFS and similar path search algorithms.
@@ -47,7 +48,8 @@
         graph = new AdjacencyListsGraph<>(vertexes(), edges());
 
         GraphPathSearch<TestVertex, TestEdge> search = graphSearch();
-        Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, H, weight).paths();
+        Set<Path<TestVertex, TestEdge>> paths =
+                search.search(graph, A, H, weight, ALL_PATHS).paths();
         assertEquals("incorrect paths count", 1, paths.size());
 
         Path p = paths.iterator().next();
@@ -56,7 +58,7 @@
         assertEquals("incorrect path length", pathLength, p.edges().size());
         assertEquals("incorrect path cost", pathCost, p.cost(), 0.1);
 
-        paths = search.search(graph, A, null, weight).paths();
+        paths = search.search(graph, A, null, weight, ALL_PATHS).paths();
         printPaths(paths);
         assertEquals("incorrect paths count", pathCount, paths.size());
     }
@@ -68,7 +70,7 @@
                                  EdgeWeight<TestVertex, TestEdge> weight,
                                  int pathCount, double pathCost) {
         GraphPathSearch.Result<TestVertex, TestEdge> result =
-                search.search(graph, src, dst, weight);
+                search.search(graph, src, dst, weight, ALL_PATHS);
         Set<Path<TestVertex, TestEdge>> paths = result.paths();
         printPaths(paths);
         assertEquals("incorrect paths count", pathCount, paths.size());
@@ -78,4 +80,21 @@
         }
     }
 
+    // Executes the single-path search and validates its results.
+    protected void executeSinglePathSearch(GraphPathSearch<TestVertex, TestEdge> search,
+                                           Graph<TestVertex, TestEdge> graph,
+                                           TestVertex src, TestVertex dst,
+                                           EdgeWeight<TestVertex, TestEdge> weight,
+                                           int pathCount, double pathCost) {
+        GraphPathSearch.Result<TestVertex, TestEdge> result =
+                search.search(graph, src, dst, weight, 1);
+        Set<Path<TestVertex, TestEdge>> paths = result.paths();
+        printPaths(paths);
+        assertEquals("incorrect paths count", Math.min(pathCount, 1), paths.size());
+        if (pathCount > 0) {
+            Path<TestVertex, TestEdge> path = paths.iterator().next();
+            assertEquals("incorrect path cost", pathCost, path.cost(), 0.1);
+        }
+    }
+
 }
diff --git a/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
index d225377..5348bf6 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DepthFirstSearchTest.java
@@ -22,6 +22,7 @@
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertTrue;
 import static org.onlab.graph.DepthFirstSearch.EdgeType;
+import static org.onlab.graph.GraphPathSearch.ALL_PATHS;
 
 /**
  * Test of the DFS algorithm.
@@ -52,7 +53,7 @@
         DepthFirstSearch<TestVertex, TestEdge> search = graphSearch();
 
         DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult result =
-                search.search(graph, A, H, weight);
+                search.search(graph, A, H, weight, 1);
         Set<Path<TestVertex, TestEdge>> paths = result.paths();
         assertEquals("incorrect path count", 1, paths.size());
 
@@ -77,7 +78,7 @@
 
         // Perform narrow path search to a specific destination.
         DepthFirstSearch<TestVertex, TestEdge>.SpanningTreeResult result =
-                search.search(graph, A, null, weight);
+                search.search(graph, A, null, weight, ALL_PATHS);
         assertEquals("incorrect paths count", 7, result.paths().size());
 
         int[] types = new int[]{0, 0, 0, 0};
diff --git a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
index e11ccb2..d906e65 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
@@ -55,16 +55,16 @@
                                              new TestEdge(C, D, 1),
                                              new TestEdge(D, C, 1)));
         GraphPathSearch<TestVertex, TestEdge> gs = graphSearch();
-        Set<Path<TestVertex, TestEdge>> paths = gs.search(graph, A, B, weight).paths();
+        Set<Path<TestVertex, TestEdge>> paths = gs.search(graph, A, B, weight, 1).paths();
         printPaths(paths);
         assertEquals("incorrect paths count", 1, paths.size());
         assertEquals("incorrect path cost", 1.0, paths.iterator().next().cost(), 0.1);
 
-        paths = gs.search(graph, A, D, weight).paths();
+        paths = gs.search(graph, A, D, weight, 1).paths();
         printPaths(paths);
         assertEquals("incorrect paths count", 0, paths.size());
 
-        paths = gs.search(graph, A, null, weight).paths();
+        paths = gs.search(graph, A, null, weight, 1).paths();
         printPaths(paths);
         assertEquals("incorrect paths count", 1, paths.size());
         assertEquals("incorrect path cost", 1.0, paths.iterator().next().cost(), 0.1);
@@ -78,6 +78,7 @@
                                              new TestEdge(B, D, 1),
                                              new TestEdge(C, D, 1)));
         executeSearch(graphSearch(), graph, A, D, weight, 2, 2.0);
+        executeSinglePathSearch(graphSearch(), graph, A, D, weight, 1, 2.0);
     }
 
     @Test
@@ -93,6 +94,7 @@
                                              new TestEdge(F, G, 1),
                                              new TestEdge(A, G, 4)));
         executeSearch(graphSearch(), graph, A, G, weight, 5, 4.0);
+        executeSinglePathSearch(graphSearch(), graph, A, G, weight, 1, 4.0);
     }
 
     @Test
@@ -106,6 +108,7 @@
                                              new TestEdge(F, G, 1), new TestEdge(F, H, 1),
                                              new TestEdge(A, E, 3), new TestEdge(B, D, 1)));
         executeSearch(graphSearch(), graph, A, E, weight, 3, 3.0);
+        executeSinglePathSearch(graphSearch(), graph, A, E, weight, 1, 3.0);
     }
 
     @Test
@@ -123,6 +126,7 @@
                                              new TestEdge(G, A, -5),
                                              new TestEdge(A, G, 4)));
         executeSearch(graphSearch(), graph, A, G, weight, 3, 4.0);
+        executeSinglePathSearch(graphSearch(), graph, A, G, weight, 1, 4.0);
     }
 
     @Test