Let us consider a plain search algorithm (Dijkstra being one example) which will calculate the shortest path from A to B.

Now introduce the additional constraint that the path must be as close as possible to a third point, C, without necessarily going through it (thus breaking down the route into an A–C and a C–B portion would not work).

A real-world example would be “go from Munich to Lyon via Milan”: a human driver would not take this as a requirement to pass through downtown Milan, but would understand that the route over San Bernardino and through the Fréjus tunnel is preferred over the route along the shores of Lac Léman.

For a route graph, this could be phrased as “find the path from A to B which has the least sum of length and shortest distance between C and any point on the path”.

Is there a standard algorithm (or variation of a standard algorithm, Dijkstra preferred) which satisfies that constraint?

  • $\begingroup$ The way we would do this on google maps is to create a required point on our path near Milan and let it calculate the best A-C-B path. Google maps already penalizes the downtown streets for traffic and whatnot. So why not have, in your algorithm, some number of acceptable spots C(i) around the cities to avoid, and use dijkstra to solve the shortest A-C(i)-B paths and choose the C(i) giving the best one $\endgroup$
    – JimN
    Dec 14, 2017 at 23:15
  • $\begingroup$ Can you ask a more specific question? I'm sure an algorithm exists. Are you happy with any algorithm? Are you happy with any polynomial-time algorithm? Do you want the most efficient algorithm possible? What's the best algorithm you've found so far? By the way, why does it matter whether the algorithm is "standard" or not? If it solves the problem, shouldn't that be good enough? $\endgroup$
    – D.W.
    Dec 15, 2017 at 2:59
  • 1
    $\begingroup$ I think it'd work if you simply kept two distances per node - the regular one, and the min-dist-to-C seen so far. The total cost (for priority) is then their sum, and you compute the first normally and the second with min(). $\endgroup$
    – xs0
    Dec 15, 2017 at 11:52


Your Answer

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

Browse other questions tagged or ask your own question.