diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/topology/impl/DefaultTopology.java b/core/store/dist/src/main/java/org/onlab/onos/store/topology/impl/DefaultTopology.java
index 939e558..3ee7ae2 100644
--- a/core/store/dist/src/main/java/org/onlab/onos/store/topology/impl/DefaultTopology.java
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/topology/impl/DefaultTopology.java
@@ -262,9 +262,16 @@
      * @return set of shortest paths
      */
     Set<Path> getPaths(DeviceId src, DeviceId dst, LinkWeight weight) {
+        final DefaultTopologyVertex srcV = new DefaultTopologyVertex(src);
+        final DefaultTopologyVertex dstV = new DefaultTopologyVertex(dst);
+        Set<TopologyVertex> vertices = graph.getVertexes();
+        if (!vertices.contains(srcV) || !vertices.contains(dstV)) {
+            // src or dst not part of the current graph
+            return ImmutableSet.of();
+        }
+
         GraphPathSearch.Result<TopologyVertex, TopologyEdge> result =
-                DIJKSTRA.search(graph, new DefaultTopologyVertex(src),
-                                new DefaultTopologyVertex(dst), weight);
+                DIJKSTRA.search(graph, srcV, dstV, weight);
         ImmutableSet.Builder<Path> builder = ImmutableSet.builder();
         for (org.onlab.graph.Path<TopologyVertex, TopologyEdge> path : result.paths()) {
             builder.add(networkPath(path));