# Route finding on a graph that must go through multiple edges

I have this graph It shows a graph of a map that has nodes and segments (or edges), with weights, that connect these nodes. Some of these segments have addresses on, and some of these addresses are designated as restaurants. There are two chosen restaurants, and one chosen address.

Can someone point me in the direction of an algorithm that would calculate the best path to get from any segment, through each of the segments containing the chosen restaurants, and ending at the chosen address?

So far I have looked at Christofides Algorithm, and Dijkstra's Algorithm, neither of which seem to solve this problem, or atleast i cannot work out how to alter the algorithms to make them work for this problem.

• For such a small instance, you can probably solve this exactly using integer programming. Jan 8, 2021 at 15:08
• Practically speaking, I would just run a known TSP algorithm and remove the edge touching the chosen endpoint. There is also a reduction from your problem to TSP that I gave in comments to your two preceding posts, but it loses the planar nature of your problem. Jan 8, 2021 at 15:27
• Your points live on the Euclidean plane, and this potentially makes your problem easier to solve (compared to a general metric). Jan 8, 2021 at 15:33
• You can use a TSP solver as part of a larger application. Indeed, I suspect that this is typically how a TSP solver is used. There are many open-source TSP solvers you could use. Jan 8, 2021 at 15:48
• It would really help if you could ballpark the number of chosen restaurants. It should be very doable to have up towards 15 restaurants with the classic DP algorithm. If you accept approximation algorithms, you can get a much faster algorithm handling hundreds of restaurants (as @YuvalFilmus says, on the plane). Jan 8, 2021 at 16:15

Subdividing an edge $$e = uv$$ means that you create a new vertex $$v_e$$ with $$u$$ and $$v$$ as neighbors, and then you delete the edge $$e$$ from the resulting graph. If the edges are weighted, there should be no issue in putting $$w(e)/2$$ on each of the two new edges (depending a bit on what the weights mean).
In the case where you only have a handful of, say, "terminals" (your restaurants), the very easily implementable classic exact DP algorithm running in $$O(2^t t^2 \cdot (n+m))$$ time should be very feasible (say for $$t \leq 12$$).