Questions tagged [shortest-path]

The Shortest Path is the shortest or least-cost path from a source or set of sources to a destination or set of destinations. It can often be implemented in vector or raster GIS and is often desired in network analysis such as the shortest path to a location along the road network.

61 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
2answers
89 views

Shortest path touching all points

I am looking for a solution to derive the shortest route that touches all the points using Python. Please note that This is not a Travelling salesman problem (TSP), in which the route should end ...
3
votes
0answers
65 views

Shortest line network route between clusters of points and the cluster centroid

I have a point layer containing clusters of points (premises) that I have grouped using a clustering algorithm (the clusters each having their own unique ID which I have used to create convex hull ...
3
votes
0answers
93 views

Shortest path (point to point) in iteration

I am using Network Analysis-> Shortest path (point to point) to compute the distance between two points, following a network from OSM. It works like magic for single requests, but I do not seem to be ...
3
votes
0answers
117 views

Finding path between points on limited road network

I am struggling to find a path between health facilities in Madagascar. I think that because the road network (from OpenStreetMap) is limited, the functions in QGIS, such as v.net.distance and ...
3
votes
0answers
230 views

Network analysis: shortest path to 'visit' all polygons

I'm totally new to QGIS but I really like it and would like to solve something more elaborated. I found a lot of threads and tutorials about how to solve the traveling salesman problem with QGIS but ...
3
votes
0answers
357 views

Route between two point layers following streets

I have a problem to be solved with shortest path route. What I have: layer 1 with startpoints layer 2 with endpoints layer 3 with streets (lines) These two point layers are originally the start ...
3
votes
0answers
168 views

Optimum Path finding (for Cross Country Movement) using TIN

I am working on path finding algorithm (using A*) for cross country movement (not for road movement) on map using grid based approach. Algorithm supports path calculation considering slope of terrain. ...
2
votes
1answer
44 views

Shortest path points layer to points layer

i'd like to know how can i get in QGIS the shortest path from a points layer to points layer, according to field values. In QGIS, I've seen only the function "from vector to single point" ...
2
votes
0answers
108 views

QGIS Shortest path (point to layer) start point expression in modeller

When in QGIS I run processing tool Shortest path (point to layer) ... I am satisfied with the result (below picture red line). But when I try to run the same tool in QGIS modeller, the result is ...
2
votes
0answers
197 views

Using shortest path pgr_dijkstra

Versions PostGIS Bundle 3 for PostgreSQL x64 12 pgAdmin 4.24 pgrouting 3.1.0 I have also enabled the postgis and pgrouting extensions on a public schema. I am only just starting with pgrouting so I am ...
2
votes
0answers
49 views

Shortest path from one to many points to return path id's using QGIS

I'm trying to find the shortest path between many points (pink) and one point (light green) using a network of lines (dark green). For each path found I need the list of line id's that make that path. ...
2
votes
0answers
55 views

Shortest path for a series of points

I have a points layer with bus stop locations and a line layer which represents the road network. I want to find the shortest path for each bus route based on the sequence of bus stops and save the ...
2
votes
0answers
42 views

How to make output generated from shortest path in QGIS more reasonable

My goal is to generate bus route stop by stop given the bus route and stops with sequence number of single direction. I tried to achieve this by using shortest path in QGIS stop by stop. However, ...
2
votes
0answers
365 views

Connecting points to lines via network layer in QGIS

So I have a set of three layers: A set of points A road network layer A line layer (e.g. which represents a cable) I need to find the shortest paths which connect the points (Layer 1) to the line ...
2
votes
1answer
268 views

Speed up the shortest distance calculation using pgRouting + PostGIS

I have to calculate the shortest path and corresponding distances for 300k+ origin-destination (OD) pairs. Using the query below it takes me around 0.3 sec to calculate one distance and therefore more ...
2
votes
1answer
207 views

K-shortest path between two points in QGIS

I am new to QGIS. I have a road network layer in QGIS. I can compute the shortest path between the two points over the road network layer via the Network Analysis toolbox in QGIS. I am interested in ...
2
votes
1answer
127 views

Yen's or Eppstein for path with intermediate destinations which are dangling nodes

I'm trying to find a shortest path algorithm (which does not need to be optimal) for a path with intermediate destinations. Consider the following case: One wants to go from A to Z and in between ...
2
votes
0answers
221 views

Calculation of fastest path with in network analysis by qgis 3.0

I have a road network (with speed limit) and different points connected to the roads. I would like to measure the distance between several points along the roads. Basically I want to do shortest path ...
2
votes
0answers
346 views

Shortest network to connect multiple points (Euclidean Steiner Tree problem)

I have a shapefile (Houses.shp) with points representing houses in a village (from 10 to 40 houses per village). I want to connect the houses in each village to each other with the shortest possible ...
2
votes
0answers
32 views

How to assign costs for turns on GRASS vector network analysis?

I would like to get a better understanding of how to assign costs for turns when creating a least-cost path with GRASS network tools, basically because I don't want any line to be used twice for ...
2
votes
0answers
114 views

How do I measure shortest distance where it crosses +/- 180 (the International Date line)

I'm trying to measure the shortest distance between two sets of points on the globe in QGIS. One set of points is close to -180 and the other close to +180, QGIS Distance matrix is giving me a ...
2
votes
0answers
229 views

How to find shortest line from a point on a polygon boundary to a multilinestring, but the line is inside polygon (PostGIS)

I have 3 geometries 1 polygon 1 point on boundary 1 multilinestring In this image you can see the problem. I need to find shortest line from point (green square) to line (red), but the line must be ...
2
votes
0answers
348 views

Automate Running Shortest Path

I have to use a qgis method (python, plugin, scripts) only to automate a shortest path calculation for multiple start and end points. How might i automate the shortest path road graph tool?
2
votes
0answers
296 views

Shortest path calculation from shapefile data using GeoTools?

I'm using geotools 14.3 with swing to load two shape files. A road network and a node network (road junctions). Objective I want to calculate the shortest path from each node to every other node. I'...
2
votes
0answers
133 views

Shortest path tool failed in QGIS

I'm trying to find the shortest path between two points (green and red points) on a road layer using QGIS 2.12.3. The roads layer has appropriate CRS. Before sign the "start" and "end" points I ...
2
votes
0answers
428 views

How to calculate best path between 2 points from a DEM in Qgis?

I'm analyzing the roads and paths of a region by calculating how effective the communication is in the region. First I calculated the shortest paths between the points using the actual road map. Now ...
1
vote
0answers
36 views

Finding shortest line ("arc") traversing a road

Is there any existing method (Qgis plugin, PostGIS etc.) to find the best (shortest) line (arc) to follow in order to traverse a road (represented as polygonal area)? If not, what algorithmic approach ...
1
vote
1answer
70 views

Calculating shortest path using two network layers in PyQGIS

Using PyQGIS I can calculate the shortest path from point to point. But I need to calculate the shortest path based on two network layers: A and B. So that the result should be the shortest path from ...
1
vote
0answers
40 views

How to connect / 'join' lines selectively but automatically in QGIS

I had a similar problem a while back with How to join (draw new) lines that are close but not touching - large dataset This is the same dataset, however I found a problem with what I did before. The ...
1
vote
0answers
18 views

Calculation of intermediate points along shortest path not working correctly

I am trying to implement the calculation of points along the shortest path using the algorithm shown here: LatLng getGreatCirclePoint(double lat1, double lon1, double lat2, double lon2) { double d = ...
1
vote
0answers
63 views

Qgis Shortest Path Facility problem

My aim is to calculate the shortest distance between two point layers One point layer contains Origin points, the other point layer contains Destination points. Both layers contain more than 100 data ...
1
vote
0answers
34 views

Network Analysis Shortest path with original line segments as output

I've managed to batch run the shortest path algorithm and the shortest route (point to layer) in the output is perfect, except that I really need the individual attribute tables of the line segments ...
1
vote
0answers
29 views

Shortest Path between large area -- RAM issue

I built a shortest path algorithm that finds and stores the distance of the optimal path between neighboring grid cells using a friction surface as an input. It works beautifully but I am facing RAM ...
1
vote
1answer
430 views

Combining the output of ST_Collect/ST_Union to create linestring from multilinestring?

I am using pgr_dijkstra() to compute the shortest path and then using ST_Collect (or ST_Union) to get the shortest path geometry. However, the collection returned from the ST_Collect is a multi-...
1
vote
0answers
241 views

Reporting distances to polygon features along river network using QGIS?

I am using QGIS 3.6 on windows 10. I am trying to work out a way of reporting on the distances to polygon features (ecological sites) located along a river network. I have extracted the shortest path ...
1
vote
0answers
109 views

Qneat3 / shortest distance calc sensitive to altitude?

I'm trying to calculate shortest distance using Qneat3 (using both the shortest path and OD-matrices for different purposes). And am wondering if there is any possobility to factor in altitide (it is ...
1
vote
0answers
136 views

How to create a line through contours?

I am using QGIS 2.18.14. I want to create line through contour lines with fixed segments, automatically. I already tried manually with 'Advanced Digitizing Tools'. It works fine but too slow. The ...
1
vote
0answers
424 views

How to find least cost path subject to distance constraint?

I have a raster with each cell representing a travel cost. I need to find the least cost path from one point on the raster to another point on the raster. One additional twist: the path cannot exceed ...
1
vote
0answers
193 views

How to find shortest paths between one destination and multiple origins in ArcGIS?

I am working on landfill site analysis. I have a landfill site (point) in my data. I want to connect the landfill point with different locations(points) in my study area using shortest paths. I have ...
1
vote
0answers
37 views

Finding the arcs traversed in Shortest Path (Network Analyst) - ArcGIS

I used Shortest Path from Network Analyst in ArcGIS to calculate the shortest distances between multiple points. The result I get is the length of the paths, but what I need is the actual route in ...
1
vote
0answers
73 views

polylines between two locations over sea and not land

I have several thousand locations in a database, Location A travelling to Location B, New York to London, Paris to Buenos Aires. I'm trying to plot a path between two places only over sea. I'm not ...
1
vote
0answers
237 views

Road Graph doesn't find shortest path

Road Graph plugin in QGIS does not find the shortest path except when the feature is a single line. This might be due to the fact that I've used different CRS for layer and project while I edited the ...
1
vote
1answer
385 views

Getting two lat-lon points in JSP to find shortest path on click of OpenLayers map?

I'm using GeoServer, PostgreSQL and here OpenLayers. I'm trying to retrieve two lat-lon points (for point A and point B) on clicking of map. This code is working only to retrieve one lat-lon. I ...
1
vote
0answers
155 views

Shortest Path Between Points for Airborne Travel

I work for an aerial surveying firm and have a point shapefile of every location we need to fly over to survey. There are approximately 500 features in this dataset. I would like to determine the ...
1
vote
0answers
422 views

Creating a Raster of Road Distance to Point

I am using QGIS 2.6. This question is in two related parts: I'm trying to create a raster of travel time from one point to another point travelling via the road system. Each raster pixel will roughly ...
1
vote
1answer
483 views

How to build a shortest spanning trees that respects existing connections using QGIS?

I have a) a point layer of connection points to an existing network, i.e. an existing network can be accessed here. b) a point layer of sites that should be connected newly to the existing network ...
0
votes
0answers
42 views

Shortest-path algorithms used in Networkx: what about points not near nodes?

I am new to Networkx, but am I right that Dijkstra's is the algorithm Networkx uses by default? From what I understand, Dijkstra's algorithm traces a shortest path between two nodes on a graph. What, ...
0
votes
0answers
18 views

Output from Mean coordinate to input of shortest path in model

I'm building a model in QGIS 3 and I want to be able to "feed" the output of Mean Coordinate to the input "Start point" of Shortest Path. The issue is that in Shortest Path I ...
0
votes
0answers
26 views

Finding the point closest to a point in another feature class and the paths between them

There are two point feature classes (let's call them Sinks and Sources). Working with ArcGIS Desktop, I need to find, for each Sink, its nearest Source. Normally I'd do a spatial join, but this time I ...
0
votes
0answers
91 views

Shortest road route calculation on OpenLayers GeoDjango

I have created a web based GIS application using Django, Mapnik, Mapproxy, OpenLayers 6. Now I need to develop a shortest path(road distance) between two points selected by the user. What is the best ...