Java – Which k-best shortest-path algorithms should I consider

Dijkstra's finds the shortest path between a given node and all other nodes, so I expect it would be more expensive than A*. However, it looks like you're trying to pre-compute the cost & path from any node to any other? Then Dijkstra's is the way to go.

As for a simpler representation, a few things come to mind:

At many intersections, you can come & leave any way you want. It's only a a subset that you have restrictions like "no left turn." So you could use the "laths" only for intersections where you actually need them. That should greatly reduce the size right there.

You could do this automatically by looking for "equivalent laths" and combining them. Two laths are equivalent if all the links coming out are the same. E.g. if "Intersection X coming from the West" and "Intersection X coming from the South" both lead to the same set of other nodes, with the same cost, then just merge them into a single node.

Are you sure you need/want to precompute the best path, instead of computing it online? Video games typically compute these things online.

Also, how are you representing the paths? In your matrix, you only need to represent the first link in the path. For example, to get from Bob's house to Bob's work, you only need to know the first link, since when they get there, you can now look in your matrix for how to get from the first link to Bob's work, which will give you the second link, etc.

Here's an implementation that I dug up from when I was dealing with graphs. Although it's in C#, with a few minor adjustments it could compile in Java.

To make it directed you would have to copy v.Adjacents.Add(new Edge(w, cost)); and reverse the direction, thereby taking up double the space.

I don't think it's any better than what you have though.

class Edge
{
    public Vertex Destination { get; set; }
    public double Cost { get; set; }

    public Edge(Vertex destination, double cost)
    {
        Destination = destination;
        Cost = cost;
    }

}

class Vertex
{
    public string Name { get; set; }
    public List<Edge> Adjacents { get; set; }
    public double Distance { get; set; }

    public Vertex(string name)
    {
        Name = name;
        Adjacents = new List<Edge>();
        Distance = double.MaxValue;
    }
}

class Graf
{
    private readonly Dictionary<string, Vertex> vertexmap = new Dictionary<string, Vertex>();

    public void AddEdge(string source, string dest, double cost)
    {
        var v = GetVertex(source);
        var w = GetVertex(dest);
        v.Adjacents.Add(new Edge(w, cost));
    }

    private Vertex GetVertex(string vertexname)
    {
        Vertex v;
        vertexmap.TryGetValue(vertexname, out v);
        if (v == null)
        {
            v = new Vertex(vertexname);
            vertexmap.Add(vertexname, v);
        }
        return v;
    }
}