Efficiency and design of Dijkstra's algorithm modified for connected nodes

Question

I've written an AI (well... it's not really that intelligent) that plays the board game Ticket to Ride. In that game, cities are essentially nodes of a graph, linked together by train tracks (the edges of the graph). The goal is form routes between cities, but it doesn't matter how circuitous or direct a route is as long as it's unbroken.

The set of potential locations for tracks is limited, and different tracks have different costs. To assist my AI in deciding where to place tracks, I wrote the following modified version of Dijkstra's shortest path algorithm. The difference between it and the "normal" Dijkstra is that it accounts for cities that are already connected to each other, similar to what was described in this Programmers SE question. Groups of connected cities in between the "target" cities are treated similarly.

protected Stack<City> getShortestPath(Set<City> startSubgraph, Set<City> endSubgraph) {
 List<DijkstraCity> unvisited = new LinkedList<DijkstraCity>();
 EnumMap<City, DijkstraCity> dijkstraCities = new EnumMap<City, DijkstraCity>(City.class);
 initializeDijkstra(unvisited, dijkstraCities);
 initializeDijkstraDistances(dijkstraCities, startSubgraph);
 while (continueDijkstra(unvisited, endSubgraph)) {
 Collections.sort(unvisited);
 DijkstraCity currentDc = unvisited.get(0); // Depends on unvisited being sorted
 City currentName = currentDc.name;
 CityNode currentCn = board.getCityByName(currentName);
 // For each neighbor: see if unvisited and path available
 // If so, calculate tentative distance
 // If tentative distance less than current best, save as new best
 Set<City> neighbors = currentCn.getNeighbors();
 int currentBaseDist = currentDc.tentativeDist;
 for (City neighbor : neighbors) {
 // Has the city already been visited?
 DijkstraCity neighborDc = dijkstraCities.get(neighbor);
 if (!unvisited.contains(neighborDc))
 continue;
 // Is a path/route to the city even open to this player?
 if (board.getRoutesForPlayer(currentName, neighbor, this) == null)
 continue;
 // At this point, city is unvisited and route is available
 // Calculate distance
 int distFromCurrent = currentBaseDist + currentCn.getLengthToNeighbor(neighbor);
 if (distFromCurrent < neighborDc.tentativeDist) {
 neighborDc.tentativeDist = distFromCurrent;
 neighborDc.previous = currentDc;
 }
 // Since it's possible for the player to already own routes
 // between the start and endpoints, add an extra check
 DijkstraCity connectedDc = null;
 for (Set<City> cityGroup : connectedCities) {
 if (cityGroup.contains(neighbor)) {
 for (City connectedCity : cityGroup) {
 connectedDc = dijkstraCities.get(connectedCity);
 if (connectedDc.tentativeDist > neighborDc.tentativeDist) {
 connectedDc.tentativeDist = neighborDc.tentativeDist;
 connectedDc.previous = neighborDc; // This can cause the returned path to include non-adjacent cities!
 }
 }
 }
 }
 }
 // If all unvisited cities are at MAX_VALUE after the neighbors of
 // the current city have been checked, the destination is
 // unreachable, and we should abort
 if (currentDc.tentativeDist == Integer.MAX_VALUE)
 return null;
 // Mark the city we just completed as visited before next loop
 unvisited.remove(currentDc);
 }
 // Leaving the above loop = all necessary cities visited
 // Almost done, we just need to determine where the end is now...
 int lowestPathToEnd = Integer.MAX_VALUE;
 DijkstraCity endCity = null;
 for (City endCandidate : endSubgraph) {
 DijkstraCity endCandidateDc = dijkstraCities.get(endCandidate);
 if (endCandidateDc.tentativeDist < lowestPathToEnd) {
 lowestPathToEnd = endCandidateDc.tentativeDist;
 endCity = endCandidateDc;
 }
 }
 // ...and finally follow the path back to the start.
 Stack<City> shortestPath = new Stack<City>();
 do {
 shortestPath.push(endCity.name);
 endCity = endCity.previous;
 } while (endCity != null);
 return shortestPath;
}

Here are the two helper methods used at the beginning, and the loop condition:

private void initializeDijkstra(List<DijkstraCity> unvisited, EnumMap<City, DijkstraCity> dijkstraMap) {
 DijkstraCity van = new DijkstraCity(VANCOUVER);
 DijkstraCity sea = new DijkstraCity(SEATTLE);
 // and so on for the other cities on the board; cut just to save space
 unvisited.add(van);
 unvisited.add(sea);
 // and so on for the other cities on the board; cut just to save space
 dijkstraMap.put(VANCOUVER, van);
 dijkstraMap.put(SEATTLE, sea);
 // and so on for the other cities on the board; cut just to save space
}
private void initializeDijkstraDistances(EnumMap<City, DijkstraCity> dijkstraCities, Set<City> startCityNames) {
 for (City city : startCityNames)
 dijkstraCities.get(city).tentativeDist = 0;
}
/**
 * Technically, we only have to run until all of the cities in "unvisited"
 * are also in "endSubgraph," but checking for that would be a pain, so
 * we'll save that micro-optimization for later.
 */
private boolean continueDijkstra(List<DijkstraCity> unvisited, Set<City> endSubgraph) {
 return !unvisited.isEmpty();
}

This is the helper class referenced by the method above

public class DijkstraCity implements Comparable<DijkstraCity> {
 public City name;
 public int tentativeDist;
 public DijkstraCity previous;
 public DijkstraCity(City name) {
 this.name = name;
 tentativeDist = Integer.MAX_VALUE;
 previous = null;
 }
 @Override
 public int compareTo(DijkstraCity otherCity) {
 return tentativeDist - otherCity.tentativeDist;
 }
 @Override
 public String toString() {
 return name.toString();
 }
}

The Dijkstra method and its helpers are located within an abstract Player class. City is an Enum that just lists the cities in the game (VANCOUVER, SEATTLE, etc.). All the collections used are the "standard" versions found in java.util.

I'm mostly interested in how I could have done this in a more efficient or elegant way.

Answer 1

private void initializeDijkstra(List<DijkstraCity> unvisited,
 EnumMap<City, DijkstraCity> dijkstraMap) {
 DijkstraCity van = new DijkstraCity(VANCOUVER);
 DijkstraCity sea = new DijkstraCity(SEATTLE);
 // and so on for the other cities on the board; cut just to save space
 ...
}

No. To save space, use a loop:

private void initializeDijkstra(List<DijkstraCity> unvisited,
 EnumMap<City, DijkstraCity> dijkstraMap) {
 for (City city : City.values) {
 DijkstraCity dijkstraCity = new DijkstraCity(city);
 unvisited.add(dijkstraCity);
 dijkstraMap.put(city, dijkstraCity);
 }
}

---

Actually, I'd recommend to use no enum here. Enums are nice for things which need no flexibility, but one day you may want to play a different map.

Even if there are no other maps and the producer got bankrupt and the author started drinking and whatever, I would not use an enum as I can always imagine, there can be more.

---

Use final. In

public class DijkstraCity implements Comparable<DijkstraCity> {
 public City name;
 public int tentativeDist;
 public DijkstraCity previous;
 ...
}

at least name should be final (I'd also call it "city" instead).

---

A Comparable where the result of compareTo can change in time is a bad thing. If you ever create a TreeSet<DijkstraCity> or a PriorityQueue<DisjktraCity>, it will blow badly. For such cases, I'd suggest to use Comparator instead. It doesn't really help, but it's considered to be a lesser sin.

---

Actually, the algorithm longs for a PriorityQueue. It could replace your sorting inside of the loop in

while (continueDijkstra(unvisited, endSubgraph)) {
 Collections.sort(unvisited);

Sorting all cities only to get the minimum is rather inefficient, but a PriorityQueue can't be used with objects whose compareTo changes. I'm sure, there's a solution, but can't recall it now. I'll update my answer when I find it out.

No really good idea for the PriorityQueue

Instead of sorting, it's surely better to find the single element needed (i.e., the minimum). A PriorityQueue can be used assuming the following:

• make DijkstraCity immutable
• if a shorter distance is found, enqueue a new DijkstraCity
• upon encounter of an already processed city, ignore it

This leads to duplicates in the queue, but it shouldn't really matter. Alternatively, you could remove an element and add a new one, but this would be surely much slower (the removal is O(n)). You could instead watch the size of the queue, and re-create it if it grows too much (let's say 5x the proper size).

You could use a TreeSet, which would work well with the removal (O(log n)). However, I guess, the PriorityQueue would be faster despite the duplicates.

• Davish: I'd be very interested in hearing your update about the priority queue. I struggled with that a lot when I was writing the algorithm and was never really happy with my workaround of sorting on every iteration when a maximum of one item would be out of order. Also, guess I should have said in the initial question, there are no other maps available for this game.
• Davish: Ohhh, yeah! As long as memory isn't an issue -- and it's certainly not, in my case -- that's a really clever solution to the heap/sorting issue in your edit!
• maaartinus: @Davish The bigger heap is a bit slower, but not much as it's only logarithmic. Anyway, cleaning it if it really grows too big would solve it. I don't know how fast it grows and I'd really consider cleaning in case of a thousand cities.

Answer 2

I believe (I have not tried it) that you can indeed simplify your code. You can code the normal Dijkstra algorithm, or use an available implementation.

The tricky bit is to define correctly what your "nodes" actually are, and how to compute their "distance". You can use Set<City> as your node type. And the distance between Set<City> node1 and Set<City> node2 can be defined as the minimum cost between all pairs from those two sets.

• Davish: Could you please be more specific? If I understand you, then this gets exponentially less efficient as more cities get added to the start and end sets. (Actually, this feels like an answer to the linked Programmers question.)
• toto2: I had not looked at the link. It seems to be what was suggested in a comment. It is not less efficient: computing the "distance" between two "nodes" indeed is slower, but you have less "nodes".