###No really good idea for the PriorityQueue
No really good idea for the PriorityQueue
###No really good idea for the PriorityQueue
No really good idea for the PriorityQueue
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.
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
DijkstraCityimmutable - 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.
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.
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.
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
DijkstraCityimmutable - 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.
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.
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.