Improving time complexity of cheapest travel route algorithm

Question

Below is the code to find the cheapest route for a passenger. stationsUnexplored is a Queue to which stations are added and examined. Once we are done with a station, it is removed from Queue and added to a Set stationsExplored. The purpose of stationsExplored is to avoid queuing of stations more than once. Before adding a station to stationsUnexplored I check if it has been explored earlier i.e !stationsExplored.contains(adjacentStation.getKey(). Or it is already present in the queue i.e !stationsUnexplored.contains(adjacentStation.getKey()). First contains() is on a Set, so it has time complexity of \$\mathcal{O}(1)\$. But second contains() is called on a Queue hence the time complexity is \$\mathcal{O}(N)\$.

Is there a way to get rid of the second check on queue or improve it to \$\mathcal{O}(1)\$?

 Queue<Integer> stationsUnexplored = new ArrayDeque<>();
 Set<Integer> stationsExplored = new HashSet<>();
 stationsUnexplored.add(1);
 while (!stationsUnexplored.isEmpty()) { 
 int currentStation = stationsUnexplored.remove();
 Map<Integer, Integer> stations = stationsNFares.get(currentStation); // returns neighboring stations.
 if (stations != null) {
 Iterator<Map.Entry<Integer, Integer>> stationIterator = stations.entrySet().iterator();
 while (stationIterator.hasNext()) { 
 Map.Entry<Integer, Integer> adjacentStation = stationIterator.next();
 // code for computing cheapest fare for current adjacent station.....
 if (!stationsExplored.contains(adjacentStation.getKey()) && !stationsUnexplored.contains(adjacentStation.getKey())) { //O(N)
 stationsUnexplored.add(adjacentStation.getKey());
 }
 }
 }
 stationsExplored.add(currentStation);
 }

• genisage: Where is adjacentStation coming from? I'm guessing you meant to include something like adjacentStation = stationIterator.next() in your loop, since as it is the variable appears out of nowhere. And to answer your question, why not just remove it from stationsUnexplored when you add it to your queue and get rid of the second check?
• Meena Chaudhary: @genisage yeah missed that line of code, now it has been added. didn't get your suggestion though can you explain with maybe piece of code.

Answer 1

I find it a little bit confusing that the title of your question doesn't seem to match its content. That is, you mention you're looking for the cheapest route, and your code sort of references fares, but your algorithm is a BFS that pays no attention whatsoever to the costs.

That said, the question you actually asked has a fairly simple answer. Change this bit of code:

if (!stationsExplored.contains(adjacentStation.getKey()) && !stationsUnexplored.contains(adjacentStation.getKey())) {
 stationsUnexplored.add(adjacentStation.getKey());
}

To this:

if ( !stationsExplored.contains(adjacentStation.getKey()) ) {
 stationsUnexplored.add(adjacentStation.getKey());
 stationsExplored.add(adjacentStation.getKey());
}

You'll also have to add a stationsExplored.add(1) around the top and you should remove the stationsExplored.add(currentStation) from the bottom. (That was wrong anyway I think. It ought to have been currentStation.getKey())

All you want is to add everything to the Queue exactly once, and this accomplishes that just as well as what you had before. It doesn't matter to your code if you mark the station as explored as soon as you add it to your Queue or if you wait until you pop it off, and by adding it early, you allow yourself to use only the faster Set contains method.

• Meena Chaudhary: I omitted the cheapest fare logic from the code as it was irrelevant to the problem at hand.