Dijkstra's shortest path algorithm in Groovy

Groovy is really great for trying out algorithms without having to write tons of code.

The other day we were elaborating over how to make a route planner for public transport.
In its simplest form, this can be solved by using Dijkstra's shortest path algorithm.

But I couldn't find any groovy versions of this algorithm. I found a decent java version (I've copied parts from it, see see Renaud Waldura's blog), but the amount of code is still measured in pages, not lines of code.

With groovy, I think, we're approaching the simplicity of the algorithm.

class DijkstrasShortestPathAlgoritm {
    def graph, start, destination    
    // PriorityQueue performs much better than List - O(log(n)) for poll.    
    def unsettledNodes = new PriorityQueue<String>(100, new Comparator<String>() {
       public int compare(String node1, String node2) {
            shortestDistance(node1).compareTo(shortestDistance(node2))
        }
    });
    def shortestDistances = [:]
    def predecessors = [:]
    def settledNodes = [] as Set

    DijkstrasShortestPathAlgoritm(graph, start, destination) {
        this.graph = graph
        this.start = start
        this.destination = destination

        unsettledNodes.add(start)
        shortestDistances[(start)] = 0
    }

    int shortestDistance(node) {
        shortestDistances.containsKey(node) ? shortestDistances[node] : Integer.MAX_VALUE
    }

    def extractMin() {
        unsettledNodes.poll()
    }

    def unsettledNeighbours(node) {
        graph.findAll { edge ->
            edge.node1 == node && !settledNodes.contains(edge.node2)
        }
    }

    def relaxNeighbours(node) {
        unsettledNeighbours(node).each { edge ->
            if (shortestDistance(edge.node2) > shortestDistance(edge.node1) + edge.distance) {
                shortestDistances[edge.node2] = shortestDistance(edge.node1) + edge.distance
                predecessors[edge.node2] = edge.node1
                if (!unsettledNodes.contains(edge.node2)) {
                    unsettledNodes.add(edge.node2)
                }
            }
        }
    }

    def calculateShortestPath() {
        while (!unsettledNodes.isEmpty()) {
            String node = extractMin()
            if (node == destination) {
                break
            }
            settledNodes += node
            relaxNeighbours(node)
        }
        shortestDistances[destination]
    }

    private def getShortestPath(node, path) {
        node == start ? [node]+path : getShortestPath(predecessors[node], [node]+path)
    }
    
    def getShortestPath() {
        getShortestPath(destination, []) 
    }
}

And then, to find the shortest path of a graph, you do like this:

class Edge {
    String node1, node2
    int distance
}
graph = [
    new Edge(node1:'a', node2:'b', distance:4),
    new Edge(node1:'a', node2:'c', distance:2),
    new Edge(node1:'b', node2:'c', distance:3),
    new Edge(node1:'c', node2:'b', distance:1),
    new Edge(node1:'c', node2:'d', distance:5),
    new Edge(node1:'b', node2:'d', distance:1),
    new Edge(node1:'a', node2:'e', distance:1),
    new Edge(node1:'e', node2:'d', distance:4)
]
def dijkstra = new DijkstrasShortestPathAlgoritm(graph, 'a', 'd')
d = dijkstra.calculateShortestPath();
assert d == 4
assert dijkstra.shortestPath == ['a','c','b','d']

Of course, the public transport domain have a lot of special rules, such as favouring routes with few connections, indirect connections made by walking between stops, buses that dont stop a specific place every second friday, etc. etc. Each and every rule may not be so difficult to solve, but the sum of the rules makes the route planner domain really complex.

Also, there are other, possibly better, algorithms for route planning, one of them being the A* algorithm.