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
0
votes
1answer
22 views

Finding the distance between two coordinates (longitudes/latitudes) which are not found as nodes in OSM

I intend to make my own OSM Router, and I do not want to use third party OSM routers. WHAT I HAVE DONE: I have downloaded OSM data in XML format and applied different algorithms to find the shortest ...
0
votes
0answers
14 views

Incorrect result when using v.net.distance on grass76

As shown in the image below I need to connect the points in yellow to the respective nearest point in brown via the shortest path on the road network in blue. I decided to use v.net.distance on ...
1
vote
1answer
46 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-...
2
votes
1answer
70 views

pgr_dijkstra gives wacky routes sometimes with undirected graph

I am using the function below to find the shortest path between several origin-destination pairs, and it seems to work correctly most of the time. CREATE OR REPLACE FUNCTION public.sp_od( orig ...
0
votes
0answers
27 views

The shortest path is not shown correctly at the time box

I am trying to find the shortest path using "Road Graph Plugin" in QGIS 2.18.22. When I set the Criterion as "Length", the length is shown but the time is not shown and it is shown as "infh". What ...
2
votes
0answers
28 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 ...
1
vote
1answer
41 views

Creating connected network of roads from overlapping roads using R?

I am trying to create a dataset of roads data to do shortest path analysis. To do this, my roads data needs to be connected: it should be possible to jump from one road to another. I am planning to ...
0
votes
0answers
18 views

Nearest Neighbour along a route instead of geographical displacement

Say that I have three layers as follows for a certain region: Line Layer representing roads Point Layer representing hotels Point Layer representing train stations Using QGIS is there a way in which ...
1
vote
0answers
32 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 ...
1
vote
0answers
24 views

Memory efficient shortest path algorithm for offline Android app [closed]

Finding the shortest path in a road network requires the road network to be loaded up in memory. Using Dijkstra's algorithm, for example, it searches through all the immediate road coordinates and ...
4
votes
0answers
80 views

Finding easiest path to walk on topographic map?

I want to make the shortest path between two points, but the thing is that there's a hill in the middle. I used Naismith's rule to calculate how the slope interfers in the walking time and I did the ...
3
votes
1answer
61 views

Cost-distance shortest path

I want to compute the shortest paths travelling overland between the origin (Africa) and destination (North America). My goal is to recreate human migration, and the shortest path should be across the ...
1
vote
0answers
65 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
1answer
51 views

networkx shortest path error

I am trying to implement single_source_dijkstra_path algorithm of the networkx to define the shortest path from a node to all nodes in the network. There are six sources in total, and I want to ...
3
votes
0answers
72 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 ...
0
votes
0answers
74 views

OD-matrix (QNEAT3) doesnt return values for all input parameters in QGIS?

I'm running into problems trying to calculate shortest distance from point (smaller black dots below in image) to a port (tagged MANAUS below). Im using hte QNEAT3 OD-matrix tool (from layers as lines)...
1
vote
1answer
62 views

PyQGIS3 retrieving points from a shortestpath graph

I'm upgrading some code which worked with QGIS 2.18 to now work with QGIS 3.4.5 and had the following snippet working to retrieve a set of points from a graph created by the QgsGraphBuilder function: ...
1
vote
0answers
68 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 ...
0
votes
0answers
45 views

Shortest path without any segment line and topography

I would like to create the shortest lines between destinations. I do not have any segment lines, so I can not use the network analyst tool. I tried another command, cost path, however, I have issues ...
4
votes
1answer
183 views

Dijkstra/Finding shortest path gives back a tree with only -1 in it

So I'm trying to implement a routing algorithm in my QGIS 3 plugin that I'm writing using Python. I think I could resolve all the problems concerning the break between QGIS 2 and 3, but my resulting ...
0
votes
0answers
76 views

Find all Shorthest Paths between 262 Points

Is there anyway to find all shortest paths between 262 points in ArcMap ? I have tried to use new route analysis in ArcMap, but it did not work. I could not understand what is the problem. I am ...
7
votes
3answers
742 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....
1
vote
2answers
101 views

Looping through a table to allocate kids to nearest school

The general problem is to allocate town's kids to their nearest school and get the distance and the geometry. Tools in use is Postgresql 10.6, PostGIS 2.4.3 and PGRouting 2.5.2 There are three ...
0
votes
1answer
29 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', ...
1
vote
0answers
265 views

Connect points to a line with shortest distance using QGIS?

On the picture below, I want to let my point connect to the line with the shortest distance and show the distance to me. I tried NNjoin, MMQGIS, v.distance But I still can't get the distance. How do ...
0
votes
0answers
48 views

GRASS GIS Shortest path: Limit on number of calculations?

I'm trying to compute the shortest path between about 10'000 location-pairs. I've prepared my vector map as described in the documentation. I can calculate shortest path on about 1'000 location pairs ...
3
votes
2answers
67 views

Can Ksp Algorithm(Shortest Path Algorithm) have a constraint that the suggested paths must include a particular node or link

I am using pgr_ksp algorithm to find out the shortest path between a startnode and endnode by creating a network topology between all the nodes. Pgr_ksp algorithm very well gives me all the shortest ...
1
vote
1answer
384 views

QGIS 3 Shortest Path: batch processing?

I have some commuting data showing people who cycle to work. The data has residence, workplace and unique ID numbers for each commuter. I have georeferenced the home and work locations so I have two ...
1
vote
2answers
820 views

Network analysis, fastest path in QGIS 3.2

I used this plugin and got results in the cost field, but I do not know in which units the cost is displayed (€, $ ...). Whether it's money or something else?
1
vote
1answer
167 views

Find shortest path and save it with geometry

With the guide of Network analysis library I found the shortest route on the network I'm analyzing. The script I used is as follows: from qgis.core import * from qgis.gui import * from qgis....
3
votes
1answer
767 views

Distance of a Lat long from a Polyline

I am currently looking for a solution where i need to find if a lat long is on the route or not. I cannot use Google Maps Geometry IsLocationOnEdge() or ContainsLocation() api's as i am working on a ...
3
votes
1answer
438 views

QGIS 3 - Shortest path layer to layer, not point!

I'm trying to build a model that will calculate the shortest path from several origins to one destination. So I have 3 georeferenced vector layers: A line road network A point layer containing ...
0
votes
0answers
71 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 ...
1
vote
0answers
144 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 ...
0
votes
0answers
261 views

how do I enter start point in shortest path algorithm in QGIS 3.0.1?

Are the x and y values displayed by the Vertex Editor (bottom left of image) not the same as the x and y values in my TestNetwork layer required by the Shortest path algorithm?
0
votes
0answers
456 views

draw path on indoor map using geoJSON avoiding obstacles

I'm a CS student and right now I'm developing an android app that uses google maps API, the problem is the map I'm working on is indoor and I'm facing problems when I want to draw a path from user ...
3
votes
0answers
180 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 ...
1
vote
0answers
203 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 ...
1
vote
1answer
87 views

nodes geographic coordinates with pgRouting Query

Can we get the coordinate of nodes belongs to shortest path??? I give brief description, I calculate the shortest path with A* algorithm using Pgrouting, but what I'm looking for coordinates (long, ...
1
vote
0answers
78 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
2answers
688 views

delete segments from road layer - QGIS

I have a road layer, with two locations points. I have created a shortest path analysis between these points. Now, I would like to delete some segment from the road network. I would like to delete (...
2
votes
0answers
23 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
1answer
467 views

Draw shortest line between a point and a line

I am trying to draw a line between a thousands of points and a line using QGIS. I then want to carry out some calculations on the new lines to see which polygons they intersect in a different layer. ...
1
vote
1answer
414 views

Getting KeyError when using shortest_path of NetworkX and ShapeFile

I have a shapefile of all street segments in Los Angeles County that I have made sure is clean. I am able to use the QGIS Road Graph plugin to calculate various shortest paths, see attached as my ...
2
votes
2answers
452 views

Shortest path between cities without duplicate calculation (many-to-many)

I have three tables ==> ways, nodes and cities (OpenStreetMap) ways : Edges with required attributes for routing (source, target, cost, etc.) nodes : Each and every nodes linking the edges cities : ...
0
votes
1answer
118 views

Finding the shortest path with online services in QGIS

I am looking for a plugin that can detriment the shortest path between two points in QGIS. It should not be a street line between the points, but the shortest way with consideration to the roads of ...
0
votes
1answer
246 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 ...
3
votes
0answers
269 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 ...
4
votes
1answer
317 views

creating a visibility graph on a sphere

I maintain a Python package (Pyvisgraph) that builds a visibility graph given set of simple obstacle polygons. I am using it to calculate shortest paths between two points on a map. The obstacles are ...
3
votes
1answer
98 views

pgrouting - Choosing an algorithm with a predominance for a specific type of road

I would like to use one of pgrouting's algorithm to find the (shortest) path between 2 points with predominance for a specific type of road. To build the data I used the osm2pgrouting. Is there an ...