diff --git a/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java
new file mode 100644
index 0000000..513c686
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/BellmanFordGraphSearch.java
@@ -0,0 +1,45 @@
+package org.onlab.graph;
+
+/**
+ * Bellman-Ford graph search algorithm for locating shortest-paths in
+ * directed graphs that may contain negative cycles.
+ */
+public class BellmanFordGraphSearch<V extends Vertex, E extends Edge<V>>
+        extends AbstractGraphPathSearch<V, E> {
+
+    @Override
+    public Result<V, E> search(Graph<V, E> graph, V src, V dst,
+                               EdgeWeight<V, E> weight) {
+        checkArguments(graph, src, dst);
+
+        // Prepare the graph search result.
+        DefaultResult result = new DefaultResult(src, dst);
+
+        // The source vertex has cost 0, of course.
+        result.updateVertex(src, null, 0.0, true);
+
+        int max = graph.getVertexes().size() - 1;
+        for (int i = 0; i < max; i++) {
+            // Relax, if possible, all egress edges of the current vertex.
+            for (E edge : graph.getEdges()) {
+                if (result.hasCost(edge.src())) {
+                    result.relaxEdge(edge, result.cost(edge.src()), weight);
+                }
+            }
+        }
+
+        // Remove any vertexes reached by traversing edges with negative weights.
+        for (E edge : graph.getEdges()) {
+            if (result.hasCost(edge.src())) {
+                if (result.relaxEdge(edge, result.cost(edge.src()), weight)) {
+                    result.removeVertex(edge.dst());
+                }
+            }
+        }
+
+        // Finally, but the paths on the search result and return.
+        result.buildPaths();
+        return result;
+    }
+
+}
diff --git a/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java b/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java
index c02afea..daf8ca2 100644
--- a/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java
@@ -10,7 +10,8 @@
         extends AbstractGraphPathSearch<V, E> {
 
     @Override
-    public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> ew) {
+    public Result<V, E> search(Graph<V, E> graph, V src, V dst,
+                               EdgeWeight<V, E> weight) {
         checkArguments(graph, src, dst);
 
         // Prepare the graph result.
@@ -18,7 +19,7 @@
 
         // Setup the starting frontier with the source as the sole vertex.
         Set<V> frontier = new HashSet<>();
-        result.costs.put(src, 0.0);
+        result.updateVertex(src, null, 0.0, true);
         frontier.add(src);
 
         boolean reachedEnd = false;
@@ -35,9 +36,8 @@
                     V nextVertex = edge.dst();
                     if (!result.hasCost(nextVertex)) {
                         // If this vertex has not been visited yet, update it.
-                        result.updateVertex(nextVertex, edge,
-                                            cost + (ew == null ? 1.0 : ew.weight(edge)),
-                                            true);
+                        double newCost = cost + (weight == null ? 1.0 : weight.weight(edge));
+                        result.updateVertex(nextVertex, edge, newCost, true);
                         // If we have reached our intended destination, bail.
                         if (nextVertex.equals(dst)) {
                             reachedEnd = true;
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 dc71859..535da09 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
@@ -12,8 +12,9 @@
         extends AbstractGraphPathSearch<V, E> {
 
     @Override
-    public Result<V, E> search(Graph<V, E> g, V src, V dst, EdgeWeight<V, E> ew) {
-        checkArguments(g, src, dst);
+    public Result<V, E> search(Graph<V, E> graph, V src, V dst,
+                               EdgeWeight<V, E> weight) {
+        checkArguments(graph, src, dst);
 
         // Use the default result to remember cumulative costs and parent
         // edges to each each respective vertex.
@@ -25,7 +26,7 @@
         // 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.
-        Heap<V> minQueue = createMinQueue(g.getVertexes(),
+        Heap<V> minQueue = createMinQueue(graph.getVertexes(),
                                           new PathCostComparator(result));
         while (!minQueue.isEmpty()) {
             // Get the nearest vertex
@@ -38,8 +39,8 @@
             double cost = result.cost(nearest);
             if (cost < Double.MAX_VALUE) {
                 // If the vertex is reachable, relax all its egress edges.
-                for (E e : g.getEdgesFrom(nearest)) {
-                    result.relaxEdge(e, cost, ew);
+                for (E e : graph.getEdgesFrom(nearest)) {
+                    result.relaxEdge(e, cost, weight);
                 }
             }
 
diff --git a/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java b/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
new file mode 100644
index 0000000..4ee9006
--- /dev/null
+++ b/utils/misc/src/test/java/org/onlab/graph/BellmanFordGraphSearchTest.java
@@ -0,0 +1,61 @@
+package org.onlab.graph;
+
+import org.junit.Test;
+
+import java.util.HashSet;
+import java.util.Set;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Test of the Bellman-Ford algorithm.
+ */
+public class BellmanFordGraphSearchTest extends BreadthFirstSearchTest {
+
+    @Override
+    protected AbstractGraphPathSearch<TestVertex, TestEdge> graphSearch() {
+        return new BellmanFordGraphSearch<>();
+    }
+
+    @Test
+    @Override
+    public void defaultGraphTest() {
+        executeDefaultTest(7, 5, 5.0);
+    }
+
+    @Test
+    public void defaultHopCountWeight() {
+        weight = null;
+        executeDefaultTest(10, 3, 3.0);
+    }
+
+    @Test
+    public void searchGraphWithNegativeCycles() {
+        Set<TestVertex> vertexes = new HashSet<>(vertices());
+        vertexes.add(Z);
+
+        Set<TestEdge> edges = new HashSet<>(edges());
+        edges.add(new TestEdge(G, Z, 1.0));
+        edges.add(new TestEdge(Z, G, -2.0));
+
+        g = new AdjacencyListsGraph<>(vertexes, edges);
+
+        GraphPathSearch<TestVertex, TestEdge> search = graphSearch();
+        Set<Path<TestVertex, TestEdge>> paths = search.search(g, A, H, weight).paths();
+        assertEquals("incorrect paths count", 1, paths.size());
+
+        Path p = paths.iterator().next();
+        assertEquals("incorrect src", A, p.src());
+        assertEquals("incorrect dst", H, p.dst());
+        assertEquals("incorrect path length", 5, p.edges().size());
+        assertEquals("incorrect path cost", 5.0, p.cost(), 0.1);
+
+        paths = search.search(g, A, G, weight).paths();
+        assertEquals("incorrect paths count", 0, paths.size());
+
+        paths = search.search(g, A, null, weight).paths();
+        printPaths(paths);
+        assertEquals("incorrect paths count", 6, paths.size());
+    }
+
+}
diff --git a/utils/misc/src/test/java/org/onlab/graph/GraphTest.java b/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
index a95af93..44b1137 100644
--- a/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
+++ b/utils/misc/src/test/java/org/onlab/graph/GraphTest.java
@@ -17,6 +17,7 @@
     static final TestVertex F = new TestVertex("F");
     static final TestVertex G = new TestVertex("G");
     static final TestVertex H = new TestVertex("H");
+    static final TestVertex Z = new TestVertex("Z");
 
     protected Graph<TestVertex, TestEdge> g;