diff --git a/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
index e0628c1..eada84c 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
@@ -38,6 +38,11 @@
         // Cost to reach the source vertex is 0 of course.
         result.updateVertex(src, null, 0.0, false);
 
+        if (graph.getEdges().isEmpty()) {
+            result.buildPaths();
+            return result;
+        }
+
         // Use the min priority queue to progressively find each nearest
         // vertex until we reach the desired destination, if one was given,
         // or until we reach all possible destinations.
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 eceeab4..e11ccb2 100644
--- a/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/DijkstraGraphSearchTest.java
@@ -17,6 +17,8 @@
 
 import org.junit.Test;
 
+import java.text.DecimalFormat;
+import java.util.HashSet;
 import java.util.Set;
 
 import static com.google.common.collect.ImmutableSet.of;
@@ -123,4 +125,37 @@
         executeSearch(graphSearch(), graph, A, G, weight, 3, 4.0);
     }
 
+    @Test
+    public void disconnectedPerf() {
+        disconnected();
+        disconnected();
+        disconnected();
+        disconnected();
+        disconnected();
+        disconnected();
+        disconnected();
+        disconnected();
+        disconnected();
+        disconnected();
+    }
+
+
+    @Test
+    public void disconnected() {
+        Set<TestVertex> vertexes = new HashSet<>();
+        for (int i = 0; i < 200; i++) {
+            vertexes.add(new TestVertex("v" + i));
+        }
+
+        graph = new AdjacencyListsGraph<>(vertexes, of());
+
+        long start = System.nanoTime();
+        for (TestVertex src : vertexes) {
+            executeSearch(graphSearch(), graph, src, null, null, 0, 0);
+        }
+        long end = System.nanoTime();
+        DecimalFormat fmt = new DecimalFormat("#,###");
+        System.out.println("Compute cost is " + fmt.format(end - start) + " nanos");
+    }
+
 }