Skip to main content

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.

Filter by
Sorted by
Tagged with
2 votes
1 answer
58 views

How to snap a line on a 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 ...
TC_Blue's user avatar
  • 29
0 votes
0 answers
39 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) ...
Akhilesh jj's user avatar
1 vote
0 answers
16 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 ...
Vincent Monteil's user avatar
0 votes
0 answers
38 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 ...
Lord_Verulam's user avatar
1 vote
1 answer
74 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 ...
sttipa's user avatar
  • 197
0 votes
0 answers
16 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 ...
Alex's user avatar
  • 1
0 votes
0 answers
30 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 ...
rzk's user avatar
  • 1
0 votes
0 answers
36 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. ...
30136353's user avatar
0 votes
0 answers
42 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 ...
Joe G's user avatar
  • 191
0 votes
0 answers
65 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 ...
redhat's user avatar
  • 347
3 votes
3 answers
641 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 ...
redhat's user avatar
  • 347
0 votes
0 answers
22 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 ...
user236225's user avatar
0 votes
0 answers
52 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 ...
Rasmus Kierudsen's user avatar
2 votes
1 answer
161 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 ...
Will's user avatar
  • 23
0 votes
1 answer
34 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 ...
SPet's user avatar
  • 141
1 vote
1 answer
61 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 ...
analyst92's user avatar
  • 847
1 vote
0 answers
215 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 ...
ibdmn's user avatar
  • 191
0 votes
1 answer
416 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 ...
T.A's user avatar
  • 1
1 vote
1 answer
25 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 ...
SPet's user avatar
  • 141
0 votes
1 answer
144 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" ...
lena's user avatar
  • 179
2 votes
0 answers
64 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 ...
Nandula's user avatar
  • 783
5 votes
1 answer
317 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 ...
winnewoerp's user avatar
  • 1,504
2 votes
1 answer
294 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: ...
Scott Allinson's user avatar
1 vote
1 answer
107 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 ...
winnewoerp's user avatar
  • 1,504
0 votes
0 answers
47 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 ...
Élie's user avatar
  • 1
2 votes
1 answer
148 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 ...
Theyyam's user avatar
  • 23
6 votes
2 answers
277 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 ...
Andre R's user avatar
  • 69
1 vote
0 answers
55 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 ...
Galv01's user avatar
  • 53
0 votes
1 answer
660 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 ...
Josip G's user avatar
  • 125
2 votes
1 answer
107 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 ...
adi schneider's user avatar
2 votes
1 answer
500 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 ...
GIS_Lenovo's user avatar
1 vote
0 answers
138 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 ...
Joel Damian's user avatar
1 vote
1 answer
398 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 ...
Guest's user avatar
  • 31
3 votes
1 answer
675 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 ...
bjornasm's user avatar
  • 196
2 votes
0 answers
424 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 ...
Ricky Urban's user avatar
1 vote
0 answers
135 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 ...
user214014's user avatar
1 vote
1 answer
17 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 ...
SPet's user avatar
  • 141
1 vote
1 answer
302 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 ...
Mark's user avatar
  • 975
3 votes
1 answer
385 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: ...
Babel's user avatar
  • 71.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.
Wawr's user avatar
  • 89
0 votes
0 answers
209 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 ...
Jil 's user avatar
  • 51
1 vote
0 answers
47 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, ...
Mark's user avatar
  • 975
3 votes
1 answer
63 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 ...
Jil 's user avatar
  • 51
4 votes
1 answer
674 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 (...
Melike Kaplan's user avatar
-1 votes
1 answer
37 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 ...
Kristjan Sander's user avatar
3 votes
1 answer
391 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 ...
Anas.S's user avatar
  • 223
2 votes
0 answers
69 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 ...
michael's user avatar
  • 1,809
1 vote
1 answer
263 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 ...
Mark's user avatar
  • 975
7 votes
3 answers
842 views

Calculating shortest route by road from one origin point to multiple destination points at once using PostGIS (pgrouting)

Referring to the below snapshot what is the best possible way to find the road distance from the red star node to all of the yellow nodes using PostGIS. Note: I don't have the road distance data ...
George V's user avatar
  • 339
10 votes
2 answers
4k 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 ...
rmj's user avatar
  • 407

1
2 3 4 5