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

  • 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 Feb 12 '19 at 7:10
  • No, every point should be hit once. Although this is also very interesting, thanks! – Philipp B. Feb 12 '19 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 Feb 12 '19 at 7:19
  • 3
    This is traveling salesperson problem. Going to nearest first usually works. – FelixIP Feb 12 '19 at 8:58
  • 1

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.