diff --git a/utils/misc/src/main/java/org/onlab/graph/AbstractPathSearch.java b/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
similarity index 98%
rename from utils/misc/src/main/java/org/onlab/graph/AbstractPathSearch.java
rename to utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
index b3ebbdb..7dad767 100644
--- a/utils/misc/src/main/java/org/onlab/graph/AbstractPathSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
@@ -15,7 +15,7 @@
  * @param <V> vertex type
  * @param <E> edge type
  */
-public abstract class AbstractPathSearch<V extends Vertex, E extends Edge<V>>
+public abstract class AbstractGraphPathSearch<V extends Vertex, E extends Edge<V>>
         implements GraphPathSearch<V, E> {
 
     private double samenessThreshold = 0.000000001;
diff --git a/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java b/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java
new file mode 100644
index 0000000..66dd33a
--- /dev/null
+++ b/utils/misc/src/main/java/org/onlab/graph/BreadthFirstSearch.java
@@ -0,0 +1,57 @@
+package org.onlab.graph;
+
+import java.util.HashSet;
+import java.util.Set;
+
+/**
+ * Implementation of the BFS algorithm.
+ */
+public class BreadthFirstSearch<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> ew) {
+        checkArguments(graph, src, dst);
+        
+        // Prepare the graph result.
+        DefaultResult result = new DefaultResult(src, dst);
+
+        // Setup the starting frontier with the source as the sole vertex.
+        Set<V> frontier = new HashSet<>();
+        result.costs.put(src, 0.0);
+        frontier.add(src);
+        
+        search: while (!frontier.isEmpty()) {
+            // Prepare the next frontier.
+            Set<V> next = new HashSet<>();
+
+            // Visit all vertexes in the current frontier.
+            for (V vertex : frontier) {
+                double cost = result.cost(vertex);
+                
+                // Visit all egress edges of the current frontier vertex.
+                for (E edge : graph.getEdgesFrom(vertex)) {
+                    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);
+                        // If we have reached our intended destination, bail.
+                        if (nextVertex.equals(dst))
+                            break search;
+                        next.add(nextVertex);
+                    }
+                }
+            }
+            
+            // Promote the next frontier.
+            frontier = next;
+        }
+        
+        // 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/DefaultMutablePath.java b/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java
index 0ef4f98..be7ad18 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DefaultMutablePath.java
@@ -14,8 +14,6 @@
  */
 public class DefaultMutablePath<V extends Vertex, E extends Edge<V>> implements MutablePath<V, E> {
 
-    private V src = null;
-    private V dst = null;
     private final List<E> edges = new ArrayList<>();
     private double cost = 0.0;
 
@@ -32,20 +30,18 @@
      */
     public DefaultMutablePath(Path<V, E> path) {
         checkNotNull(path, "Path cannot be null");
-        this.src = path.src();
-        this.dst = path.dst();
         this.cost = path.cost();
         edges.addAll(path.edges());
     }
 
     @Override
     public V src() {
-        return src;
+        return edges.isEmpty() ? null : edges.get(0).src();
     }
 
     @Override
     public V dst() {
-        return dst;
+        return edges.isEmpty() ? null : edges.get(edges.size() - 1).dst();
     }
 
     @Override
@@ -69,28 +65,35 @@
     }
 
     @Override
+    public void insertEdge(E edge) {
+        checkNotNull(edge, "Edge cannot be null");
+        checkArgument(edges.isEmpty() || src().equals(edge.dst()),
+                      "Edge destination must be the same as the current path source");
+        edges.add(0, edge);
+    }
+
+    @Override
     public void appendEdge(E edge) {
         checkNotNull(edge, "Edge cannot be null");
-        checkArgument(edges.isEmpty() || dst.equals(edge.src()),
+        checkArgument(edges.isEmpty() || dst().equals(edge.src()),
                       "Edge source must be the same as the current path destination");
-        dst = edge.dst();
         edges.add(edge);
     }
 
     @Override
-    public void insertEdge(E edge) {
-        checkNotNull(edge, "Edge cannot be null");
-        checkArgument(edges.isEmpty() || src.equals(edge.dst()),
-                      "Edge destination must be the same as the current path source");
-        src = edge.src();
-        edges.add(0, edge);
+    public void removeEdge(E edge) {
+        checkArgument(edge.src().equals(edge.dst()) ||
+                              edges.indexOf(edge) == 0 ||
+                              edges.lastIndexOf(edge) == edges.size() - 1,
+                      "Edge must be at start or end of path, or it must be a cyclic edge");
+        edges.remove(edge);
     }
 
     @Override
     public String toString() {
         return com.google.common.base.Objects.toStringHelper(this)
-                .add("src", src)
-                .add("dst", dst)
+                .add("src", src())
+                .add("dst", dst())
                 .add("cost", cost)
                 .add("edges", edges)
                 .toString();
@@ -98,19 +101,17 @@
 
     @Override
     public int hashCode() {
-        return Objects.hash(src, dst, edges, cost);
+        return Objects.hash(edges, cost);
     }
 
     @Override
     public boolean equals(Object obj) {
         if (obj instanceof DefaultMutablePath) {
             final DefaultMutablePath other = (DefaultMutablePath) obj;
-            return super.equals(obj) &&
-                    Objects.equals(this.src, other.src) &&
-                    Objects.equals(this.dst, other.dst) &&
-                    Objects.equals(this.cost, other.cost) &&
+            return Objects.equals(this.cost, other.cost) &&
                     Objects.equals(this.edges, other.edges);
         }
         return false;
     }
+
 }
diff --git a/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java b/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java
index b0cd098..d7fc9e8a 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DefaultPath.java
@@ -73,8 +73,7 @@
     public boolean equals(Object obj) {
         if (obj instanceof DefaultPath) {
             final DefaultPath other = (DefaultPath) obj;
-            return super.equals(obj) &&
-                    Objects.equals(this.src, other.src) &&
+            return Objects.equals(this.src, other.src) &&
                     Objects.equals(this.dst, other.dst) &&
                     Objects.equals(this.cost, other.cost) &&
                     Objects.equals(this.edges, other.edges);
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 9b27bd8..dc71859 100644
--- a/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/DijkstraGraphSearch.java
@@ -9,7 +9,7 @@
  * one, but all shortest paths between the source and destinations.
  */
 public class DijkstraGraphSearch<V extends Vertex, E extends Edge<V>>
-        extends AbstractPathSearch<V, E> {
+        extends AbstractGraphPathSearch<V, E> {
 
     @Override
     public Result<V, E> search(Graph<V, E> g, V src, V dst, EdgeWeight<V, E> ew) {
diff --git a/utils/misc/src/main/java/org/onlab/graph/MutablePath.java b/utils/misc/src/main/java/org/onlab/graph/MutablePath.java
index c0a72c9..2d8420d 100644
--- a/utils/misc/src/main/java/org/onlab/graph/MutablePath.java
+++ b/utils/misc/src/main/java/org/onlab/graph/MutablePath.java
@@ -22,6 +22,15 @@
     void appendEdge(E edge);
 
     /**
+     * Removes the specified edge. This edge must be either at the start or
+     * at the end of the path, or it must be a cyclic edge in order not to
+     * violate the contiguous path property.
+     *
+     * @param edge edge to be removed
+     */
+    void removeEdge(E edge);
+
+    /**
      * Sets the total path cost as a unit-less double.
      *
      * @param cost new path cost