This is the fifty fifth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra
We have already seen Max flow and last time we used it to ensure that the graph is connected. Today we are going to modify this approach to calculate the shortest path between two nodes.
First, we set capacity of each edge to one.
Once again, we add constraints for flow not exceeding the capacity and flow perseverance.
Next, we sum flow of outgoing edges of source vertex and we set this sum to one. We want to have exactly one path going out from the source.
We do similar thing for the target vertex — we make sure that incoming flow is equal to one.
We sum flow multiplied by the edge weight for all edges — this is our cost. We need to minimize it to have the shortest path.
This works for graphs without negative cycles. If we have negative cycle this solution may use it. If we don’t allow using a negative cycle, we get an Elementary Shortest Path Problem (ESPP) which we are not going to solve today.