How to implement Transit Node Routing with Dijkstra graph search algorithm?

786 views Asked by At

I have a public transport data structure and I need to implement k shortest paths. Currently, the edge weight is simply the distance.

The data structure is:

public class Node {
    public int id;
    public int level;
}

public class Edge {
    public int fromNodeId, toNodeId;
    public double distance;
    public double time; //might be used for quickest route
}

The data in the Edge table is for a directed graph. On loading the data, I double (and invert) the edges so that the graph is now undirected.

I was implementing standard Dijkstra, however I need k shortest paths, so I found this implementation of Yen's algorithm.

The search works as expected, but because the graph is a transport network, some results are invalid (eg. too many changes even if path is shorter).

The Node class has a level property, which has been left unused so far. This property has values (1, 2, 3), where 1 is a level 1 node (most important), 2 is a level 2 node (less important) and 3 is a level 3 node (non important).

With this information readily available, I was seeing if there's a way to refine and speed up searches... and I stumbled upon Transit Node Routing, which as far as I can understand, I need to precompute distances as follows:

  1. From each node to every level 1 node and keep the "closest"
  2. From each level 1 to every level 2 node and keep the "closest"
  3. From each level 2 to every level 2 node

This can be done by using normal Dijkstra. If I understand correctly, if I do the above, then the graph will become contracted without the need to apply other contraction algorithms.

So after the above pre-computation, will the "new" edges be added to the Edge table so that the graph has all these new distances?

Will the search query be a simple Dijkstra (or Yen's) be based on the updated graph? If not, What kind of search algorithm should be applied?

0

There are 0 answers