I have a directed graph with roughly 2000 nodes, and roughly 4000 edges. I have created an application so the people that use it can easily see the path drawn on a map, if they e.g. want to find the shortest path between two nodes. And this works as intended. However, this shortests path is based on the weights of each edge. The "problem", as I have been told, is, that sometimes they (who have done this manually for years) know that this route needs to go through a certain node. There are certain reasons for this, but nonetheless, I need to be able to force a path to go through certain nodes.
My first idea was to just run Dijkstra's from
start node to
intermediate node and then from
intermediate node to
end node, and combine the two. And in some cases, this seems to work. But as you can imagine, sometimes the second path might go through some of the edges/nodes that was used in the first path, which doesn't work.
I could probably make some modified node disjoint path work if there was only ONE intermediate node. But I am afraid that it will get quite complicated if I were to use more than that.
So I am wondering if there might be a better option to still get the shortest path, but with forced intermediate nodes in between ?
It should also be noted that computation time is not really an issue here. Nothing needs to be almost instant, and in general it seems that a graph of this magnitude is quite "small" in terms of computation time.