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

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 getShortestPath(Set startSubgraph, Set endSubgraph) {
List unvisited = new LinkedList();
EnumMap dijkstraCities = new EnumMap(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 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 p

private void initializeDijkstra(List unvisited,
        EnumMap 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 unvisited,
        EnumMap 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 {
    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 or a PriorityQueue, 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.

StackExchange Code Review Q#62865, answer score: 2