diff --git a/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java b/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
index 7dad767..4217804 100644
--- a/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
@@ -148,15 +148,22 @@
          * If possible, relax the specified edge using the supplied base cost
          * and edge-weight function.
          *
-         * @param e    edge to be relaxed
-         * @param cost base cost to reach the edge destination vertex
-         * @param ew   optional edge weight function
+         * @param e               edge to be relaxed
+         * @param cost            base cost to reach the edge destination vertex
+         * @param ew              optional edge weight function
+         * @param forbidNegatives if true negative values will forbid the link
          * @return true if the edge was relaxed; false otherwise
          */
-        boolean relaxEdge(E e, double cost, EdgeWeight<V, E> ew) {
+        boolean relaxEdge(E e, double cost, EdgeWeight<V, E> ew,
+                          boolean... forbidNegatives) {
             V v = e.dst();
             double oldCost = cost(v);
-            double newCost = cost + (ew == null ? 1.0 : ew.weight(e));
+            double hopCost = ew == null ? 1.0 : ew.weight(e);
+            if (hopCost < 0 && forbidNegatives.length == 1 && forbidNegatives[0]) {
+                return false;
+            }
+
+            double newCost = cost + hopCost;
             boolean relaxed = newCost < oldCost;
             boolean same = Math.abs(newCost - oldCost) < samenessThreshold;
             if (same || relaxed) {
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 535da09..8f1bad0 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
@@ -40,7 +40,7 @@
             if (cost < Double.MAX_VALUE) {
                 // If the vertex is reachable, relax all its egress edges.
                 for (E e : graph.getEdgesFrom(nearest)) {
-                    result.relaxEdge(e, cost, weight);
+                    result.relaxEdge(e, cost, weight, true);
                 }
             }