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.
204 questions
3
votes
1
answer
237
views
How to improve shortest path results with Dijkstra/A* on a hexagonal mesh
I am working with traversable polygons and need to calculate the shortest path across them. To do this, I generated a hexagonal mesh over the polygons, extracted the edges, and applied both Dijkstra ...
- 497
1
vote
0
answers
38
views
Create route and alternate route in QGIS shortest path
I am using shortest path to create the shortest route from a point layer of addresses to a particular point using a street line layer as the routing layer. It all works very well. What I would ...
- 11
4
votes
3
answers
159
views
Snapping line on grid / cell edges
What I want to do :
This question is about finding an equivalent path on a grid to a given line.
The following image shows what I am trying to achieve :
Starting from a generic line (in red), I want ...
- 49
0
votes
0
answers
58
views
Shortest path for multiple points from line layer (optimized path)
I am using QGIS.
I have a set of starting points (blue & red points), and I also have a vector line layer (green line).
I need to find the shortest path from starting point (blue & red points) ...
- 61
1
vote
0
answers
30
views
Using two network / roads vector layers to calculate paths / routes
I'm working on a new problem that is complex to me, although I'd not be surprise to discover that there is already a solution to it in qgis.
Here's an illustration of my problem :
I have two roads ...
- 185
0
votes
1
answer
204
views
Python: How to convert shapefile of a road network to a Complete Graph network using Networkx
How can I convert a geodataframe of LineStrings to a Complete Graph with NetworkX?
I have a geodataframe of a collection of linestrings that geographically represent a road network (purple). I have 2 ...
- 43
1
vote
1
answer
117
views
QGIS -> Model designer -> using Shortest Path (Run in Batch Process)
I'm using QGIS 3.34.0, and making a litle model using Model Designer. I have lots of tractor roads and I need to calculate distances from each crossing of two roads to the highway road. I make points ...
- 197
0
votes
0
answers
55
views
How to customize weight function based on edge attribute in Networkx shortest_path
I have created a graph representing NYC road network.
I am trying to calculate a path between two nodes using Networkx shortest_path. Running it like this works fine and I'm able to visualize the ...
- 1
0
votes
0
answers
40
views
Merge road layer.shp and underground bt layer.geojson
I would like to merge a road layer .shp and a BT souterrain.gejoson network layer to create a single layer. This will allow me to form a unified network to calculate the shortest path between two ...
- 1
0
votes
0
answers
63
views
Nearest Neighbour on route vs Shortest Path
I have a line layer “Cables” which represents my network, and this is formatted correctly so all lines are in the correct direction. I have a node layer “nodes” that sit directly on top of the lines. ...
- 11
0
votes
0
answers
55
views
QGIS Shortest Path Iteration
I have a large QGIS Fiber to the Home (FTTH) design with 727 address, my focus here is on the Lateral sections from the homes to the Handholes (shown in green).
The design roughly breaks up to four ...
- 363
0
votes
0
answers
103
views
Shortest path point to point Error
I'm new in Python and QGIS
I try to build the shortest path in a line layer and got an error "There is no route from start point to end point" because of point line projection.
I'm trying to ...
- 347
3
votes
3
answers
1k
views
Building the shortest path between two points inside polygon using QGIS
With QGIS I need to build the shortest route between two points inside a polygon. I have a vector polygon layer and I need to build a path inside it from the starting point to the ending point. How ...
- 347
0
votes
0
answers
37
views
Calculating minimum straight line distance in R
I am trying to calculate a minimum straight-line distance from the district headquarters to the nearest national highway network. I have the district headquarters latitude and longitude in a different ...
0
votes
0
answers
94
views
QGIS shortest line between features cannot return 0,0?
I have been out measuring railway tracks. I need to find any deviations from a straight line on the individual rails. I have created a line between the first and last point in my measurement (snapping ...
2
votes
1
answer
223
views
Generate shortest straight path between points and a given elevation in QGIS
I'm trying to do terrain analysis in QGIS.
I have a vector layer with equally spaced points along a slope, and these points are somewhat parallel to the coastline of a fjord:
I'm interested in ...
- 23
0
votes
1
answer
39
views
GRASS build polylines based on category/ID (v.net.distance)
I have calculated shortest routes between citywide origin-destination pairs with GRASS and v.net.distance. These routes are segmented, however, and I would like to turn them into polylines based on ...
- 141
1
vote
1
answer
70
views
Minimum spanning tree (MST) over a set of POINT geometries
I have 3 columns in my table: centerPoint (point), uuid (string), and "areaID".
Each areaID can have multiple uuid's, and each uuid has a corresponding centerPoint.
I want to calculate the ...
- 879
1
vote
0
answers
349
views
QGIS: Shortest Path (network analysis) not working properly
My task is to connect all green points with the blue point by individual lines:
I have created a path network with the following steps:
extract the data of streets and roads from OSM with the plugin ...
- 191
0
votes
1
answer
575
views
TypeError("Must pass list-like as `names`."), Network generated via osm, geopandas, momepy. Objective: Run short path analysis via osmnx
I am trying to solve short path analysis via osmnx.distance.k_shortest_paths(G, orig, dest, k, weight='length')
I have used this approach as I am limited in the SSL/memory, that is why I am not using ...
- 1
1
vote
1
answer
33
views
sDNA - randomization
I am working on a pedestrian flow model for an inner city area using sDNA and link-weighted betweenness. The network is a slightly simplified road centerline map (not OSM) where most pedestrian ...
- 141
0
votes
1
answer
206
views
Selecting lines of shortest path between two points (QGIS)
I am looking for a method to automatically select the lines of a shortest path between two points. Theoretically it is the Road Graph plugin, which is now the "shortest path point to point" ...
- 179
2
votes
0
answers
72
views
Solving the Knapsack Problem with a road network on QGIS
I have a road network with weights assigned based on building density (i.e., how many buildings consider a given road segment the closest road). E.g., in the image below red indicates road segments ...
- 783
5
votes
1
answer
463
views
Travel time for shortest path (by distance) in QGIS
I have a network with previously calculated and direction-dependent travel time for each edge (speed_fw for drawing direction and speed_bw for against drawing direction). I prepare the network in QGIS ...
- 1,601
2
votes
1
answer
309
views
How to if a polygon is within a concave area of another?
Is there a method where I can detect if a polygon is inside the concave area of another (in this case a bay), then output the bay itself?
It's hard to explain with words so I'll demonstrate below:
...
1
vote
1
answer
137
views
Setting edge drawing direction-sensitive attribute-based impedance (cost) in QGIS network analysis
I need to calculate the best cycling route using selected attributes of the network layer as cost values. Using the "Shortest Path (Point to Point)" tool for network analysis in QGIS, how ...
- 1,601
0
votes
0
answers
55
views
No path found between two points
I'm trying to find a path between different pairs of points,
But within the thousands of pairs tried only a few actually result in a path.
I find this odd but maybe it's normal.
(note that when I'm ...
- 1
2
votes
1
answer
166
views
Storing shortest path route - QGIS 3.22.9
I used the shortest path tool in QGIS 3.22 to find the shortest route from the node "1000" to node "1004" in my project. The result is shown in red around my road layers (links) in ...
- 23
6
votes
2
answers
347
views
Finding furthest point from origin point using QGIS
I'm using QGIS 3.28 and I need to find the furthest point from an certain origin.
For reference, this is a Fiber to the Home (FTTH) project.
Imported data:
The pink dot on the center is the point of ...
- 69
1
vote
0
answers
58
views
QGIS - Find the shortest path on ORS Tools
I have got two layers:
Point Layer 1 that has got random 'houses' in a town
Point Layer 2 that has got all the post offices in the town
My aim is to find the shortest path from each house from layer ...
- 53
0
votes
1
answer
882
views
QGIS Network problem - There is no route from start point to end point
I am working with QGIS 3.20.0-Odense, but the same problem persists in QGIS 3.22.16 'Białowieża'.
I am working on a distance matrix, supplemented by a vector of lines (network analisys) - The output ...
- 135
2
votes
1
answer
121
views
How to put the end points with the same rows as the start points using shortest path tool on network roads - QGIS?
I have 2 point layers containing XY in qgis and I'm trying to get the shortest paths between each rows along a given network (row1 in first layer to row1 in second layer and so on). I used this ...
2
votes
1
answer
659
views
QGIS Shortest Path Calculation (Layer to Layer)
Using QGIS, I have a task for which I need to combine 2 point layers (with x-y coordinates in it). I managed to combine the points but they are only straight and I want them to follow the street ...
- 21
1
vote
0
answers
150
views
how could I calculate the shortest distance between points showing the distance in each different route?
I want to do a network analysis using any plugin, but the main problem is that I want to get the shortest distance between two points, but it must give me the distance in each route (in my case they ...
- 11
1
vote
1
answer
485
views
Shortest distance of point feature from one line in QGIS
I would like to ask for your help with calculating in simple way distance of points feature to one line (for example, what is distance of cities from the national border).
I see there were few topics ...
- 31
3
votes
1
answer
787
views
Seeking algorithm for finding shortest path around obstacles
I am seeking an algorithm, not GIS software.
To find the shortest path between two points at sea with land between them, you can consider land as a polygon shaped obstacle between these. The concept ...
- 196
2
votes
0
answers
501
views
Connecting points with closest points (lines) avoiding polygon using QGIS
How can I connect multiple points with the closest line or point of the network avoiding polygon (land or sea) in QGIS?
There are over 4000 points that have to be connected this way so it would be ...
- 23
1
vote
0
answers
161
views
Making shortest path for number of each points with link layer in QGIS
I want to make shortest path for a number of each points with a link layer in QGIS.
Now, shortest path tool have to click the start point and end point one by one.
But I have 2,000 pairs.
So I want to ...
- 11
1
vote
1
answer
22
views
sDNA - sum of traffic along shortest path
I am trying to get a measure or proxy of the estimated aadt encountered along the shortest path. One way would be to compute shortest paths between origins (around 280) and destinations (one) via skim ...
- 141
1
vote
1
answer
375
views
How to choice a specific direction to get the shortest path
I'd like to know how to choice the left or right direction starting from a point and following a network; in the processing shortest path (from starting point to vector points layer) of QGIS. In this ...
- 995
3
votes
1
answer
509
views
"Could not write feature into OUTPUT" error when running "Shortest path (point to layer)" in QGIS
I use QGIS 3.26 with a point and a line layer, representing cities connected by a network. Running QGIS native tool "Shortest path (point to layer)", I get the following error message:
...
- 74.9k
8
votes
2
answers
2k
views
Building the shortest route through all points in QGIS
How to build the shortest route through all selected points, starting from a given point? Which plugin to use?
There is a point layer and a linear layer for all routes between points.
- 89
0
votes
0
answers
230
views
QNEAT3 OD Matrix distance incorrect?
I am currently working on calculating the distances between all pairs of NUTS-2 regions in a road network.
To accomplish this I am using the QNEAT3 plugin. It worked very efficiently and I was ...
- 51
1
vote
0
answers
52
views
Shortest path based on priority
I'm using the geoprocessing "Shortest path (from layer to point)" of QGIS and i'd like to get the shortest path not in the usually way, but based on priority of the routes used.
For example, ...
- 995
3
votes
1
answer
71
views
Calculating region pair distances along network in QGIS 3.22.4
I'm currently attempting to calculate the distances between several thousand region pairs (centroids) along the Roman road network in QGIS. I want to achieve something similar to the "Shortest ...
- 51
4
votes
1
answer
768
views
Automating the selection of starting points in calculation of Shortest path (point to layer) in QGIS
For a letter drop experiment in Germany, I am using QGIS Network Analysis tools to calculate the shortest distances from letter drop points to surrounding postboxes. Using the "Shortest path (...
-1
votes
1
answer
39
views
Vector line length vs. geographical distance (as a bird flies) [closed]
Is there a way to compare the length of a line (ESRI Shapefile in my case) to the actual distance it covers with freely available tools?
I am developing an optional path algorithm. The image below ...
3
votes
1
answer
476
views
Creating multiple routes with several stops using QGIS
I am trying to find the shortest paths given a number of points with a specific order for each path. Specifically, my point data have the following format:
I used the approved solution given in ...
- 223
2
votes
0
answers
73
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,809
1
vote
1
answer
278
views
Putting coordinates of end point in shortest path algorithm
How do I put the coordinates (x,y) of the end point of the shortest path algorithm (from vector to point) which is part of a QGIS model?
I'd like to get the calculated coordinates of a point (with the ...
- 995