Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

3
votes
1answer
37 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
55 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
27 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
57 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
32 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
38 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
33 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
42 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
132 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
72 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
509 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
90 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
25 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
191 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
41 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
60 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
303 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
670 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
138 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
613 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
349 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
66 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
131 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
250 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
399 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
159 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
185 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
70 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
70 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
522 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
21 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
383 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
374 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
411 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
113 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
219 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
244 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
287 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
85 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 ...
1
vote
1answer
302 views

Implementing qgis shortest path feature in map

I have drawn routes on my map in QGIS tool and I checked in using QGIS shortest path tool. I imported the map with the help of qgis2web plugin but when I open the map it has no option for the routes I ...
6
votes
1answer
507 views

How to connect nodes via shortest path along network lines with GRASS v.net modules?

My goal: I would like to connect several nodes via the shortest path along a network --> The red nodes in the next image should be connected along the shortest path of the yellow lines. My approach:...
1
vote
0answers
227 views

How to find least cost path subject to distance constraint?

I have a raster with each cell representing a travel cost. I need to find the least cost path from one point on the raster to another point on the raster. One additional twist: the path cannot exceed ...
1
vote
0answers
158 views

How to find shortest paths between one destination and multiple origins in ArcGIS?

I am working on landfill site analysis. I have a landfill site (point) in my data. I want to connect the landfill point with different locations(points) in my study area using shortest paths. I have ...
3
votes
0answers
72 views

How do I measure shortest distance where it crosses +/- 180 (the International Date line)

I'm trying to measure the shortest distance between two sets of points on the globe in QGIS. One set of points is close to -180 and the other close to +180, QGIS Distance matrix is giving me a ...
-1
votes
1answer
713 views

How to calculate shortest path using pgrouting 2.1?

I installed postgresql 9.1.12 & created database "mydb" with user "abc" as below: sudo apt-get install postgresql-9.1 postgresql-9.1-contrib postgresql-9.1-postgis and created databse "mydb". ...
1
vote
0answers
32 views

Finding the arcs traversed in Shortest Path (Network Analyst) - ArcGIS

I used Shortest Path from Network Analyst in ArcGIS to calculate the shortest distances between multiple points. The result I get is the length of the paths, but what I need is the actual route in ...
0
votes
1answer
158 views

Left turns at major intersections

My pgRouting shortest path algorithm is able to take restrictions and oneway streets into account. Threrefore, OSM data was imported into a PostGIS database using the tool pypgroutingloader. Sadly, ...
1
vote
1answer
170 views

Typing path length using shortest path dijkstra()

I am now trying to get the length of a shortest path using dijkstra(). I need it to find all the points in my sample, which are located more than 25 km away along roads from district centres. I will ...
0
votes
1answer
533 views

Automating procedure to calculate least-cost path to destination locations from multiple source locations using ArcGIS Desktop?

I have 2 sets of locations represented by two point shapefiles in ArcGIS 10.1. My aim is to calculate the least cost path from each source location (let's call it A) to the destination locations (let'...
0
votes
1answer
719 views

Making dijkstra algorithm Shortest Path with ArcGIS for Desktop?

I am new user of ArcGIS. I have some basic knowledge such as, add data as layers, find and download map as my related study, I am also familiar with common tools in ArcGIS like joining and selection ...