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:
- From each node to every level 1 node and keep the "closest"
- From each level 1 to every level 2 node and keep the "closest"
- 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?