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
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.
- 34k
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 ...
CommunityBot
- 1
1
vote
1
answer
450
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 ...
CommunityBot
- 1
1
vote
1
answer
517
views
pgr_Dijkstra: iterate/loop through a table with multiple OD pairs one-by-one
I have a table with 2 columns: column A with the startvertex and column B with endvertex.
How can I do a OD pairs shortest path?
It is with a loop I suppose, but how can this loop be implemented ...
CommunityBot
- 1
0
votes
1
answer
576
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 ...
CommunityBot
- 1
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 ...
- 30.9k
0
votes
1
answer
284
views
ModelBuilder not giving actual result
I have 20 pairs of origin and destination. I also have 20 different line barriers for those pairs, as I want to determine the shortest path between them. If the name of the origin and destination is ...
CommunityBot
- 1
2
votes
1
answer
201
views
"Unable to execute algorithm Could not load source layer for INPUT: invalid value" when 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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
2
votes
1
answer
194
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 ...
CommunityBot
- 1
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 ...
- 20.3k
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 ...
- 74.9k
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) ...
- 20.3k
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 ...
- 65.4k
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 ...
- 77.7k
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 ...
- 1,419
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
3
votes
0
answers
357
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 ...
CommunityBot
- 1
0
votes
1
answer
162
views
Database based solution for TDSP (Fastest)
I have tried pgRouting in PostGres for finding shortest path
select d.*, bs.starttime, bs.endtime, bs.trip_id from pgr_dijkstra(
'select id, source, target, traveltime as cost from my_table',
...
CommunityBot
- 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 ...
- 239
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. ...
- 65.4k
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 ...
- 34k
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 ...
- 78k
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 ...
- 77.7k
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 ...
- 20.3k
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
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 ...
- 2,343
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" ...
- 37
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 ...
- 20.3k
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 ...
- 13k
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 ...
- 5,479
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:
...
- 77.7k
5
votes
2
answers
428
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" ...
- 74.9k
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 ...
- 74.9k
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 ...
- 65.4k
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
1
vote
2
answers
803
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-...
- 5,283
3
votes
1
answer
438
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 ...
CommunityBot
- 1
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 ...
- 4,050
11
votes
3
answers
6k
views
Shortest path between one point to every other points
I am trying to figure out how to find all the shortest paths from each point and each node of a line to the other points and nodes of lines of this map.
I have tried to do it in Python using NetworkX....
- 55.4k
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 ...
- 17.9k
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
486
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 ...
- 65.4k
4
votes
2
answers
2k
views
Creating input node file for v.net.salesman in GRASS
I have imported the line vector layer and point vector layer (12 points) to GRASS using v.in.ogr. Now I want to use v.in.salesman to find the shortest path between these 12 points, but I couldn't ...
- 91
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 ...
- 65.4k
8
votes
1
answer
2k
views
Creating optimised path between nodes avoiding polygons entities using QGIS
I have a point shapefile representing seaports. I have the linear cost of shipping for every seaport pairing (specific shipping cost to go from one point to another point). I want to find a way of ...
- 65.4k