Shortest path using Breadth First Search

I have sample graphs like the following (un-directed un-weighted cyclic graphs). My goal is to find the shortest path between a given source and destination.

I have found this implementation on web and have made some modifications only. How can the code be improved? Are there any gotchas that I need to take care of?

film--->[language, film_actor, film_category, inventory]
film_actor--->[actor, film]
store--->[customer, inventory, staff, address]
payment--->[customer, rental, staff]
actor--->[film_actor]
rental--->[payment, customer, inventory, staff]
customer--->[address, store, payment, rental]
city--->[address, country]
country--->[city]
staff--->[payment, rental, address, store]
category--->[film_category]
address--->[city, customer, staff, store]
inventory--->[film, store, rental]
film_category--->[category, film]
language--->[film]

Graph and BreadthFirstSearch classes:

Graph.java

```
package com.bfs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Graph {

/**
* Stores a list of nodes in this Graph.
*/
private ArrayList nodes = new ArrayList();

/**
* Creates a mapping from a node to its neighbours.
*/
private Map> map = new HashMap>();

/**
* Constructs a graph.
*/
public Graph() {
}

/**
* Adds an edge between two nodes.
*
* @param source the source node.
* @param destination the destination node, to be connected from source. Requires:
* source != null, destination != null.
*/
public void addEdge(String source, String destination) {
// Adds a new path.
if (!map.containsKey(source)) {
/*
Stores a list of neighbours for a node.
*/
ArrayList neighbours = new ArrayList();
neighbours.add(destination);
map.put(source, neighbours);
} else {
// Updates a path.

-
There are several places in this code where a loop is redundant(or at least can be simplified). For instance, this for loop:

int index = 0;
while ((index != oldList.size()) && (!oldList.get(index).equals(destination))) {
    index++;
}

can be substituted with a call to the contains method(the index of the element is not used, anyway. It just checks that whether an element is in the list).

This method is also way too long and complicated:

public ArrayList getNeighbours(String node) {
    ArrayList neighboursList;
    Set keys = map.keySet();
    for (String key : keys) {
        if (key.equals(node)) {
            neighboursList = map.get(key);
            return new ArrayList(neighboursList);
        }
    }
    return new ArrayList();
}

Taking into account that it requires that an element is present in the graph, we could simply write it as new ArrayList(map.get(node)).

And here:

while (index != neighboursSize) {
    String neighbour = neighboursList.get(index);

    path.add(neighbour);
    path.add(vertex);

    if (neighbour.equals(destination)) {
        return processPath(source, destination, path);
    } else {
        if (!visited.contains(neighbour)) {
            queue.offer(neighbour);
         }
    }
    index++;
}

Using a while loop to simply iterate over all elements of a collection looks strange. I'd rather use for each loop:

for (String neighbour : neighboursList) {
    // Do the same stuff.
}

In general, avoid using loops when there is a standard method for doing what you need.

-
If you are using Java 8, you can simplify the code even more by using the getOrDefault method of the Map to avoid things like:

if (map.containsKey(someKey)) {
    something = map.get(someKey);
} else {
    something = defaultValue;
}

You can also use diamond operator if you have Java 7 or later:

ArrayList list = new ArrayList<>();

to make your code more concise.

-
Prefer interfaces to concrete implementations. That is, use List instead of ArrayList unless you need some specific features of the latter.

-
Passing strings around as node identifiers make the code less understandable. I'd recommend creating a separate Node class.

StackExchange Code Review Q#84717, answer score: 9