0
$\begingroup$

I have this graph

enter image description here

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.

Improve this question
$\endgroup$
11
  • $\begingroup$ For such a small instance, you can probably solve this exactly using integer programming. $\endgroup$
    – Yuval Filmus
    Jan 8, 2021 at 15:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Jan 8, 2021 at 15:27
  • 1
    $\begingroup$ Your points live on the Euclidean plane, and this potentially makes your problem easier to solve (compared to a general metric). $\endgroup$
    – Yuval Filmus
    Jan 8, 2021 at 15:33
  • 2
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Jan 8, 2021 at 15:48
  • 1
    $\begingroup$ 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). $\endgroup$
    – Pål GD
    Jan 8, 2021 at 16:15

2 Answers 2

Reset to default
1
$\begingroup$

I have decided that the best solution to this is a variation on Dijkstra's algorithm. Since it doesn't require a Hamiltonian Circuit and makes it easy to manage the weights. I will also use Homeomorphism as suggested in the comments of the question to make weighting the distance between the nodes and addresses more accurate.

Improve this answer
$\endgroup$
1
$\begingroup$

The statement that you want a path that "goes through multiple edges" is easily replaced with a normal path finding algorithm when you observe that you can subdivide each edge containing a place of interest.

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).

Once you have done that, the problem is a standard Euclidean TSP problem. There are many approximation algorithms (a very simple 2-approximation using minimum spanning trees), as well as numerous PTAS algorithms.

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$).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.