Estoy intentando crear un método que devuelva la ruta más corta de un nodo a otro en un gráfico no ponderado. Consideré el uso de Dijkstra, pero esto parece un poco exagerado ya que solo quiero un par. En su lugar, he implementado una búsqueda de amplitud, pero el problema es que mi lista de devolución contiene algunos de los nodos que no quiero, ¿cómo puedo modificar mi código para lograr mi objetivo?Ruta más corta (menos nodos) para gráficos no ponderados
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;
}
¿Por qué no se desea que algunos de esos nodos? – mkoryak
no todos ellos pertenecen a una sola ruta de ruta más corta – Robert
¿El nodo de clase sobrescribe equal y hashcode correctamente? – mkoryak