Problem with Graph Traversal

Question

Hi

I have implemented a graph traversal algorithm which finds a path between two nodes in the graph. The problem is that it only finds a path for some queries when I know that there is a path between every node

public List getDirectRoute(Node start, Node end)
{
    //Uses Dijkstras
    List<Node> vis = new LinkedList<Node>();
    Map<Node,Node> prev = new HashMap<Node,Node>(); // Records the previous Node

    List<Node> route = new LinkedList<Node>(); //Will hold the final route
    Queue<Node> queue = new LinkedList<Node>(); // Used for the algorithm 

    Node current = start;
    queue.add(current);
    vis.add(current);

    while(!queue.isEmpty())
    {
        current = queue.remove();

        if(current.equals(end))
        {
            break;
        }else
        {
            for(Node node : successors(current) )
            {
                if(node.equals(vertices.get(0)))
                {
                    continue;
                }
                if(!vis.contains(node))
                {
                    queue.add(node);
                    vis.add(node);
                    prev.put(node, current);
                 }
             }

           }
    }

    if (!current.equals(end))
    {
        System.out.println("No route available");
    }

    for(Node node = end; node != null; node = prev.get(node))
    {
        route.add(node);

    }
    return route;


}

Am I missing something in the algorithm? I have run the debugger and but I can't find the problem

Answer 1

It looks like you're using a Breadth First Search instead of Dijkstra's algorithm to find a path from start to end. I assumed successors to return the nodes current can traverse to and vertices.get(0) to mean Nodes that do not have an outward edge to other Nodes.

With that in mind, it looks like your code should work correctly.

So I would have to say it is either your successors method that's working incorrectly or you added vertices which have edges to vertices(0) (although this can only hold 1 node).

You might get a better answer if we knew what successors did and what you store in vertices.

Answer 2

I know you're just trying to get your code to work, probably not looking for a library. But FYI, you might look at JGraphT, which is a great graph library for Java. There's a solid Dijkstra's implementation there, among other things.