Problem

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();
}
```

Solution

**Advice 1**

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

This is Θ(N)

$\mathrm{\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)

time, and you don’t need it either: just use a ** HashMap** with Θ(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

**as well in the graph node class.**

`hashCode()`

**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.