Shortest path between three points

Question

In a graph I need to find a shortest path between two points and on the way visit one checkpoint. Also, I can visit each vertex only once. I suppose it have something to do with network flow but I have no idea how to implement that.

Answer 1

You can model it entirely as a capacitated multicommodity minimum cost flow problem. You want to go from A to B via C without using a vertex twice. You can model it as a flow from A to C (commodity 1) and a flow from B to C (commodity 2). To avoid a node being used twice, you have to perform the following trick on all your nodes (in your model):

Given a node X with p incoming and t outgoing edges, you create a new node Y and rewire the links. The p incoming links will all arrive in X, the q outgoing edges will all depart from Y. Add only 1 link (L) from X to Y. By setting the capacity of the L-link to 1, each node will only be used once.

You can then write it down as an (M)ILP and have it solved. The ILP will give you the correct solution if it exists. Depending on your application, it might be overkill. If you want a fast heuristic, just use 2 A* searches and hope they don't overlap.