My Breadth-First-Search algorithm not working

Question

Can anyone help me with the BFS algorithm, I don't know what is wrong :

    public class Graph {

    private final List<City> cities;
    private final List<Route> routes;
    private final Map<City, List<Route>> myGraph = new HashMap<City,List<Route>>();       

      public Map<String,City> BFS(Graph graph, City from, City to) {
          boolean found = false;
          ArrayList<City> visited = new ArrayList<City>();
          Queue<City> toVisit = new LinkedList<City>();
          Map<String,City> rute = new HashMap<String,City>();
          toVisit.add(from);
          City node;
          while (!toVisit.isEmpty()&&(!found)) {
              node = toVisit.remove();
              visited.add(node);
              if (node.equals(to)) {
                  rute.put(node.getId(), node);
                  found = true;
              }
              else {
                  List<City> aux = new ArrayList<City>();
                  List<City> neighbors = new ArrayList<City>();
                  neighbors = this.getNeighbors(node);
                  for (City n : neighbors) 
                          aux.add(n);
                  for (City n : aux)
                      if (!visited.contains(n)&&(!n.equals(to))) {
                          rute.put(n.getId(), node);   // <--- this
                          toVisit.add(n);
                      }
             }  
          } 
//        for (int j = 0;j<rute.size();j++)
//            System.out.println(rute.get(j));
          String current = to.getId();
          StringBuffer route = new StringBuffer();
          route.append(current);
          while(current != null) {
            if (rute.containsKey(current)) {
               current = rute.get(current).getId();
               route.insert(0, current +"-->");
            } else {
               current = null;
            }
          }
          System.out.println(route);
          return rute;
      }

I need to find the shortest path between 2 cities. I would like to save all the routes in the rute map and then just check which one has the shortest distance. The problem is that after the algorithm ends rute is empty. I can't figure it out what is wrong. Please help me

Probably you should change this comparison `node == to` to `node.equals(to)`. — Luiggi Mendoza, Mar 21 '14 at 17:04

Raul Guiu · Answer 1 · 2014-03-21T17:50:31.027

0

Your problem is the visited, it is a List of Cities and you do contains in it. A Map is faster for this kind of things, and also will ensure to compare the value of the String as key.

In the Graph.BFS method replace the visited from a List by a Map:

Map visited = new HashMap();

And then:

...
while (!toVisit.isEmpty()&&(!found)) {
          node = toVisit.remove();
          visited.put(node.getId(), true); // <--- this was changed

and:

for (City n : aux)
                  if (!visited.containsKey(n.getId())&&(!n.equals(to))) {  // <-- this was changed

edited Mar 21 '14 at 17:50

answered Mar 21 '14 at 17:05

Raul Guiu

2,374
22
37

Still not working :( Maybe I should paste more of my code so you can figure it out better what is wrong? – user3421241 Mar 21 '14 at 17:12
what is key? it is not recognised – user3421241 Mar 21 '14 at 17:25
"current" sorry, i will fix it. I wrote the code here, I didnt compile it or anything. – Raul Guiu Mar 21 '14 at 17:26
It stops. I will paste all my code maybe that will help – user3421241 Mar 21 '14 at 17:29
I've updated the question with all my code. I'm trying to find the shortest path between two cities. – user3421241 Mar 21 '14 at 17:31
Now it works, but it doesn't show me the correct way( the shortest) I'm confused, I haven't used the cost from the Route class anywhere, to find out which is the shortest way.. – user3421241 Mar 21 '14 at 17:50
BFS is not the right algorith if you think about cost – Raul Guiu Mar 21 '14 at 17:51
I know, but this is the algorithm I have to use. It is a school project, and it is specified that I have to use BFS. I was thinking to save all the routes between the 2 cities in some sort of list and after the algorithm is done traversing the graph just check which distance is the smaller, but I don't know how to do it – user3421241 Mar 21 '14 at 17:59
http://stackoverflow.com/questions/8379785/how-does-a-breadth-first-search-work-when-looking-for-shortest-path-java – Raul Guiu Mar 21 '14 at 18:01
Yeah, there are talking about Dijkstra and I was specifically told not to use Dijkstra. I know the teachers are weired but this is what I'm asked. If I don't use BFS he won't even look at my project – user3421241 Mar 21 '14 at 18:05

score 0 · Answer 2 · answered Mar 21 '14 at 18:42

You should hold a reference to each node's parent. That way you can traverse back up the Graph when you find your destination.

 public class Node {
   String id;
   Node parent;
   ArrayList<Node> children;
 }

When you start at your from destination set from.parent = null. When you find your destination, traverse back via

StringBuffer path = new StringBuffer(destination.id);
Node current = destination;
while (current.parent != null) {
   path.append(current.id);
   current = current.parent;
}

This will give you the reverse path of the shortest distance between two cities. This is, of course, assuming that all of your edges have uniform costs.

My Breadth-First-Search algorithm not working

2 Answers2