Shortest Paths

Example

Here we'll try creating a graph of the North American road network found here, and find some shortest paths between points. After downloading the files listing the vertices and edges, we'll read them in to create a Graph object.

Define the Vertex Objects

Since vertices can be any object (subject to the same restrictions as those keys in a Java Map), we first define a simple vertex class representing a point in the plane.

static class Vector2 {

    final float x, y;

    Vector2(float x, float y) {
        this.x = x;
        this.y = y;
    }

    float dst (Vector2 v) {
        final float x_d = v.x - x;
        final float y_d = v.y - y;
        return (float) Math.sqrt(x_d * x_d + y_d * y_d);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Vector2 vector2 = (Vector2) o;
        return Float.compare(vector2.x, x) == 0 && Float.compare(vector2.y, y) == 0;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

Create the Graph

The files list vertices in "normalised coordinates", which means x and y values are in the range [0,10000]. We'll also save references to the point closest to the origin and furthest, and find a path between them later.

Graph<Vector2> graph = new UndirectedGraph<>();
Vector2 min = new Vector2(Float.MAX_VALUE, Float.MAX_VALUE), max = new Vector2(-Float.MAX_VALUE, -Float.MAX_VALUE);
try {
    // read vertices
    BufferedReader br = new BufferedReader(new FileReader("NA.cnode"));
    String line;
    while ((line = br.readLine()) != null) {
        if (line.charAt(0) != '#') {
            String[] split = line.split("\\s+");
            float x = Float.valueOf(split[1]), y = Float.valueOf(split[2]);
            Vector2 v = new Vector2(x, y);
            graph.addVertex(v);
            if (x < min.x && y < min.y) min = v;
            if (x > max.x && y > max.y) max = v;
        }
    }
    //Since the edges are given in terms of vertex indices, we'll save the vertices in an array, so we can reference them by index.
    Vector2[] vertices = graph.getVertices().toArray(new Vector2[0]);
    //read edges
    br = new BufferedReader(new FileReader("NA.cedge"));
    while ((line = br.readLine()) != null) {
        if (line.charAt(0) != '#') {
            String[] split = line.split("\\s+");
            int i = Integer.valueOf(split[1]) , j = Integer.valueOf(split[2]) ;
            // calculate the distance between the points in normalised coordinates
            float dst = vertices[i].dst(vertices[j]);
            graph.addEdge(vertices[i], vertices[j], dst);
        }
    }
} catch (FileNotFoundException e) {
    e.printStackTrace();
} catch (IOException e) {
    e.printStackTrace();
}
System.out.println("Graph has "+graph.size()+" vertices and "+graph.getEdgeCount()+" edges.");

We can check the vertices and edges of our graph:

System.out.println("Graph has "+graph.size()+" vertices and "+graph.getEdgeCount()+" edges.");

Graph has 175813 vertices and 179102 edges.

Finding a Shortest path

We can now easily find a shortest path from min to max:

AtomicInteger processed = new AtomicInteger();
Path<Vector2> path = graph.algorithms().findShortestPath(min, max, p -> processed.incrementAndGet());
System.out.println("The shortest path from "+min+" to "+max+" we found has "+path.size()+" vertices and length "+path.getLength()+".");
System.out.println("We processed " + processed.get() + " vertices.");

The shortest path from (3177.9458, 2191.1619) to (9604.445, 7462.6743) we found has 2724 vertices and length 11331.51.
We processed 161615 vertices.

Defining a Heuristic

Since we didn't specify a heuristic, the shortest path was found using Dijkstra's algorithm - expanding out in all directions until the target vertex is found. Since we're dealing with a graph embedded in the plane, we have extra information and can define a heuristic to allow the search to preferentially expand towards the target vertex (in which case the algorithm is called a-star). This can (though not always) result in processing fewer vertices.

AtomicInteger processed = new AtomicInteger();
Path<Vector2> path = graph.algorithms().findShortestPath(min, max, (currentNode, targetNode) -> currentNode.dst(targetNode), p -> processed.incrementAndGet());
System.out.println("The shortest path from "+min+" to "+max+" we found has "+path.size()+" vertices and length "+path.getLength()+".");
System.out.println("We processed " + processed.get() + " vertices.");

The shortest path from (3177.9458, 2191.1619) to (9604.445, 7462.6743) we found has 2724 vertices and length 11331.51.
We processed 100732 vertices.

We can see that the path we found has the same length (it is still optimal), but we didn't need to process as many vertices as we could use the heuristic to guess the right direction to go. However note that for each vertex we process we need to calculate the distance between it and the target vertex, which results in a lot of extra calculations, so it's only faster if we process far fewer vertices than the search when not providing a heuristic. It's usually best to determine this experimentally for your structures.

It's important that we choose an admissable heuristic, which means that it always returns an estimate which is at most the actual shortest path length from that vertex. If not, the optimality of the path is not guaranteed. For example, if our heuristic returns twice the distance we get The shortest path from (3177.9458, 2191.1619) to (9604.445, 7462.6743) we found has 2824 vertices and length 11907.507. which is clearly not an optimal path.

Shortest Paths

Navigation Menu