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
0answers
40 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
20 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)...
0
votes
1answer
26 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
21 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
39 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
111 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
67 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 ...
-1
votes
1answer
72 views

Using Shortest Path Network in ArcMap? [on hold]

Black points represent CSD coordinates for Canada and yellow points represents border coordinates (US/Canada). I combined these with North America major roads network. I am trying to find which black ...
7
votes
3answers
390 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
85 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
24 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
150 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
36 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
54 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
260 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
572 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
113 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
543 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
300 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
54 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
122 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
240 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
354 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
143 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
163 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
62 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
68 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
434 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
351 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
328 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
398 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
105 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
203 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
228 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
269 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
84 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
276 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
477 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
210 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
149 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
656 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
30 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
139 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
165 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
484 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
693 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 ...
2
votes
0answers
65 views

Some PostGIS functions explanations [closed]

I'm trying to optimize a route SQL function and playing with some ST_* functions I found around. But even found a good one, I don't want to simply copy/paste what someone wrote. I want to understand ...
4
votes
1answer
136 views

Calculating shortest route distances when FROM and TO are off road

I have a shapefile of ~10,000 groundwater wells, a shapefile of ~7 points of interest, and a comprehensive road network. I am looking to create a single distance value for each groundwater well that ...