2

Sorry if double post, but I haven't found this specific problem in the search function. I want qgis to show me the shortest path (direct) between many points with each point only is hit once. There is also a start point and an end point.

Given points with start and end

So that it looks like this (just an example and obviously NOT the shortest path)

enter image description here

Improve this question
6
  • Are you thinking of Djikstra's Algorithm en.wikipedia.org/wiki/Dijkstra%27s_algorithm? That does not pass through every point but does find the shortest path.. in implementation a path passing through all points is considered but discarded for being longer than a more direct path, so the same logic applies but a path only becomes valid if it passes through each point once then compare the lenghts of the valid paths and retain the shortest.
    – Michael Stimson
    Commented Feb 12, 2019 at 7:10
  • No, every point should be hit once. Although this is also very interesting, thanks!
    – Philipp B.
    Commented Feb 12, 2019 at 7:12
  • If you started with a Delaunay triangulation mathworld.wolfram.com/DelaunayTriangulation.html you could extract the edges and look at this as as a shortest path delivery problem, see en.wikipedia.org/wiki/Shortest_path_problem which lists methods (Djikstra's among them). Conceptually the edges would be the roads and points delivery locations, so none can be skipped, a shortest path is sought to minimize the travel for the driver.
    – Michael Stimson
    Commented Feb 12, 2019 at 7:19
  • 4
    This is traveling salesperson problem. Going to nearest first usually works.
    – FelixIP
    Commented Feb 12, 2019 at 8:58
  • 1
    gis.stackexchange.com/a/257299/49538
    – Fran Raga
    Commented Feb 12, 2019 at 10:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.