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
1
vote
0answers
19 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 ...
0
votes
0answers
28 views

What are the units in the network analysis

. I'm working on a project that is checking to see if distance is related to colonization by invasive species based on human activity. In order to do that, I must calculate the distances between ...
0
votes
0answers
11 views

Shortest path for a series of points

I have a points layer which is the bus stop locations and the line layer which is the road network. I want to find the shortest path for each route based on the sequence of bus stops and save the path ...
0
votes
0answers
14 views

Generate list of edges from ArcMap Python Network Analyst shortest path route

We are able to use ArcPy code to generate the shortest path route between two points in ArcMap using Network Analyst functions. Right now this just exports the shapefile of the route. What we'd like ...
0
votes
1answer
18 views

PGRouting Error Missing table?

I am trying to use pgrouting to find the shortest path in GeoServer. So I created new layer in sql view but its giving me error. I created 3 table in database: at_2po_4pgr = main table ...
0
votes
0answers
14 views

Shortest path not recognising network as connected

I'm trying to use a grid network that I have created to find the shortest path between two points accounting for directional wind-speed. The problem I'm running into is that the shortest path feature ...
0
votes
1answer
12 views

Problem with QGIS Network Analyst (Basic)

I'm going through the QGIS training (https://docs.qgis.org/3.10/en/docs/training_manual/vector_analysis/network_analysis.html) and I've encountered a problem with Network Analyst. When I open the ...
0
votes
0answers
18 views

Networkx Dijkstra Shortest Path exists but is way too long - algorithm that gives me an approximation upfront

I am computing a shortest path with networkx. Works fine most of the time, but sometimes the nodes are connected, but over a really weird very remote connection in the network. In this case the ...
1
vote
1answer
36 views

Transition Function Inputs

I would like to define my own gdistance::transition function. However, there are two issues that I aren't clear to me yet. First, I do not yet understand what the input vector to this transition() ...
1
vote
0answers
38 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 ...
0
votes
0answers
30 views

Shortest path cost units

I am using the network analysis tool to compute the shortest path between points considering a layer with roads. The problem is that I am not sure about the units of the shortest path cost. For ...
2
votes
0answers
36 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, ...
2
votes
1answer
101 views

Shortest distance for multiple starting points

I am looking to calculate the shortest distance along a road network for multiple starting points. The reason I am not doing this manually is that I have more than 5000 starting points. Does anyone ...
0
votes
0answers
21 views

Restricting the turn angles in least cost path in QGIS

I have calculated the optimum path between two points based on a DEM file; My raster cost is based on elevation and the least elevation is regarded as optimum. The output has some zigzag pattern which ...
0
votes
1answer
37 views

Iterate the shortest path point to layer

I have two layers. First layer defines the starting points and the second defines the end points. I just want to iterate the same algorithm "point to layer" by considering all the points of the first ...
0
votes
0answers
31 views

Why might Location Allocation give long paths when much shorter paths exist?

I'm using location-allocation in the network analyst toolbox of ArcMap to add features to my map. My objective function is to minimize impedance (meters). The image below shows the result. As you ...
1
vote
0answers
20 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 ...
0
votes
0answers
33 views

What method can be used to find shortest path in road network with few oneways?

I know the directional graph will be accurate in case of oneways but there are few oneways and a lot of normal ones, I can solve this with QGIS::Shortest Path(Point to Point) tool since I can define ...
1
vote
1answer
46 views

How to get path cost in A* shortest path finder of GeoTools?

I am computing a shortest path with A* algorithm of GeoTools: AStarShortestPathFinder pf = new AStarShortestPathFinder( myGraph, nodeFrom, nodeTo, myAstarfun); pf....
0
votes
1answer
190 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
24 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
158 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
112 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
30 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
120 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
191 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
32 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 ...
2
votes
1answer
96 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
44 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 ...
5
votes
0answers
104 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
2answers
114 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
107 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
101 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
85 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
210 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
91 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
89 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
51 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
286 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
77 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 ...
10
votes
3answers
2k 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
116 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
129 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', ...
4
votes
1answer
434 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 ...
3
votes
2answers
81 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
604 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
975 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
216 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
1k 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
697 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 ...