# 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
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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" ...
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 ...
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 ...
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. ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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'...
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 ...
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 ...
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 ...
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 ...
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 ...
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 = ...
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 ...
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 ...
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 ...
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...