BFS’ shortest path unweighted directed graph

The code I have is based on BFS and a little bit of Dijkstra and returns the shortest path of an unweighted directed graph as an integer. I was wondering if someone could take a look at my code too see if anything could be changed or improved:

public int bfsshortestpath (V source, V target) {
    Map<V, Integer> dist = new TreeMap<V, Integer>();
    Map<V, V> prev = new TreeMap<V, V>();

    for(V v: adjlist.keySet()){
        dist.put(v, null);
        prev.put(v, null);
    }
    dist.put(source, 0);

    Queue<V> q = new LinkedList<V>();
    q.offer(source);
    while(!q.isEmpty()){
        V u = q.poll();
        if(u == target)
            break;
        q.remove(u);
        for(V neighbor: adjlist.get(u)){
            int a = dist.get(u);
            if(dist.get(neighbor) != null)
                continue;
            //BFS distance
            dist.put(neighbor, a + 1);
            prev.put(neighbor, u);
            q.offer(neighbor);
        }
    }

    List<V> s = new LinkedList<V>();
    V u = target;
    while(prev.get(u) != null){
        s.add(u);
        u = prev.get(u);
    }
    return s.size();
}

Advice 1

for(V v: adjlist.keySet()){
    dist.put(v, null);
    prev.put(v, null);
}

This is Θ(N)

$\mathrm{\Theta }(N)$

$Theta(N)$ and you don’t really need it (see below). Also, TreeMap orders the keys (nodes) in a balanced binary search tree, which runs insertion/search/removal in worst case Θ(logn)

$\mathrm{\Theta }(\log n)$

$Theta(log n)$ time, and you don’t need it either: just use a HashMap with Θ(1)

$\mathrm{\Theta }(1)$

$Theta(1)$ access, reading and writing.

Advice 2

In order to get rid of the initialization for in the above advice, you can do:

public int shortestPathLength(V source, V target) {
    Map<V, Integer> dist = new HashMap<V, Integer>();
    Map<V, V> prev = new HashMap<V, V>();
    Queue<V> q = new LinkedList<>();

    dist.put(source, 0);
    prev.put(source, null);
    q.offer(source);

    while(!q.isEmpty()){
        V u = q.poll();
        if(u == target)
            return tracebackPath(u, prev);
        q.remove(u);
        for(V neighbor: adjlist.get(u)){
            if (!dist.containsKey(neighbor)) {                        
                dist.put(neighbor, dist.get(u) + 1);
                prev.put(neighbor, u);
                q.offer(neighbor);
            }
        }
    }

    return 0; // Target not reachable from source.
}

List<V> tracebackPath(V target, Map<V, V> prev) {
    List<V> s = new LinkedList<V>();
    V u = target;
    while(prev.get(u) != null){
        s.add(u);
        u = prev.get(u);
    }
    return s.size();
}

Advice 3

if(u == target)

Beware. I suggest you implement equals for whatever node type you use and change the above to

if (u.equals(target))

Advice 4

Since you need to map nodes to values in the HashMap s, you need to override a hashCode() as well in the graph node class.

Concluding

Suppose both target and source nodes are very close to each other. My implementation will return very fast because it does not have to run that nasty for loop.

Hope that helps.