Shortest path (fewest nodes) for unweighted graph

Question

I'm trying build a method which returns the shortest path from one node to another in an unweighted graph. I considered the use of Dijkstra's but this seems a bit overkill since I only want one pair. Instead I have implemented a breadth-first search, but the trouble is that my returning list contains some of the nodes that I don't want - how can I modify my code to achieve my goal?

public List<Node> getDirections(Node start, Node finish){
    List<Node> directions = new LinkedList<Node>();
    Queue<Node> q = new LinkedList<Node>();
    Node current = start;
    q.add(current);
    while(!q.isEmpty()){
        current = q.remove();
        directions.add(current);
        if (current.equals(finish)){
            break;
        }else{
            for(Node node : current.getOutNodes()){
                if(!q.contains(node)){
                    q.add(node);
                }
            }
        }
    }
    if (!current.equals(finish)){
        System.out.println("can't reach destination");
    }
    return directions;
}

Answer 1

Actually your code will not finish in cyclic graphs, consider graph 1 -> 2 -> 1. You must have some array where you can flag which node's you've visited already. And also for each node you can save previous nodes, from which you came. So here is correct code:

private Map<Node, Boolean>> vis = new HashMap<Node, Boolean>();

private Map<Node, Node> prev = new HashMap<Node, Node>();

public List getDirections(Node start, Node finish){
    List directions = new LinkedList();
    Queue q = new LinkedList();
    Node current = start;
    q.add(current);
    vis.put(current, true);
    while(!q.isEmpty()){
        current = q.remove();
        if (current.equals(finish)){
            break;
        }else{
            for(Node node : current.getOutNodes()){
                if(!vis.contains(node)){
                    q.add(node);
                    vis.put(node, true);
                    prev.put(node, current);
                }
            }
        }
    }
    if (!current.equals(finish)){
        System.out.println("can't reach destination");
    }
    for(Node node = finish; node != null; node = prev.get(node)) {
        directions.add(node);
    }
    directions.reverse();
    return directions;
}

Answer 2

It is really no simpler to get the answer for just one pair than for all the pairs. The usual way to calculate a shortest path is to start like you do, but make a note whenever you encounter a new node and record the previous node on the path. Then, when you reach the target node, you can follow the backlinks to the source and get the path. So, remove the directions.add(current) from the loop, and add code something like the following

Map<Node,Node> backlinks = new HashMap<Node,Node>();

in the beginning and then in the loop

if (!backlinks.containsKey(node)) {
    backlinks.add(node, current);
    q.add(node);
}

and then in the end, just construct the directions list in backwards using the backlinks map.

Answer 3

Every time through your loop, you call

directions.Add(current);

Instead, you should move that to a place where you really know you want that entry.

Answer 4

Thank you Giolekva!

I rewrote it, refactoring some:

• The collection of visited nodes doesn't have to be a map.
• For path reconstruction, the next node could be looked up, instead of the previous node, eliminating the need for reversing the directions.

public List<Node> getDirections(Node sourceNode, Node destinationNode) {
    //Initialization.
    Map<Node, Node> nextNodeMap = new HashMap<Node, Node>();
    Node currentNode = sourceNode;

    //Queue
    Queue<Node> queue = new LinkedList<Node>();
    queue.add(currentNode);

    /*
     * The set of visited nodes doesn't have to be a Map, and, since order
     * is not important, an ordered collection is not needed. HashSet is 
     * fast for add and lookup, if configured properly.
     */
    Set<Node> visitedNodes = new HashSet<Node>();
    visitedNodes.add(currentNode);

    //Search.
    while (!queue.isEmpty()) {
        currentNode = queue.remove();
        if (currentNode.equals(destinationNode)) {
            break;
        } else {
            for (Node nextNode : getChildNodes(currentNode)) {
                if (!visitedNodes.contains(nextNode)) {
                    queue.add(nextNode);
                    visitedNodes.add(nextNode);

                    //Look up of next node instead of previous.
                    nextNodeMap.put(currentNode, nextNode);
                }
            }
        }
    }

    //If all nodes are explored and the destination node hasn't been found.
    if (!currentNode.equals(destinationNode)) {
        throw new RuntimeException("No feasible path.");
    }

    //Reconstruct path. No need to reverse.
    List<Node> directions = new LinkedList<Node>();
    for (Node node = sourceNode; node != null; node = nextNodeMap.get(node)) {
        directions.add(node);
    }

    return directions;
}

Answer 5

You must include the parent node to each node when you put them on your queue. Then you can just recursively read the path from that list.

Say you want to find the shortest path from A to D in this Graph:

     /B------C------D
   /                |
 A                 /
   \             /
     \E---------

Each time you enqueue a node, keep track of the way you got here. So in step 1 B(A) E(A) is put on the queue. In step two B gets dequeued and C(B) is put on the queue etc. Its then easy to find your way back again, by just recursing "backwards".

Best way is probably to make an array as long as there are nodes and keep the links there, (which is whats usually done in ie. Dijkstra's).