Problem with Graph Traversal
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
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.
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.
精彩评论