Stack Exchange Network

Stack Exchange network consists of 174 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
Make your voice heard. Take the 2019 Developer Survey now

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.

2
votes
0answers
31 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
59 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
68 views

Using Shortest Path Network in ArcMap?

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
245 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
79 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
21 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
103 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
29 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
217 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
468 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
77 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
445 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
258 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
48 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
119 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
105 views

Shortest path in GPS coordinates

I would find the answer to this question: I have two points on earth surface, A and B, with known latitude, longitude and elevation; can I see A from B? A and B are close enough to neglect earth ...
0
votes
0answers
220 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
310 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
120 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
144 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
52 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
62 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
342 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
20 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
314 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. ...
0
votes
1answer
281 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
358 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
97 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
183 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
215 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
252 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
248 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
454 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
186 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
142 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
70 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
610 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
133 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
160 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
437 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
0answers
105 views

Creating Heat Map of 100+ shortest routes using ArcGIS Desktop?

I have 3000 polylines showing the shortest routes from 3000 different addresses to a single facility (a school. I) would like to create a heat map of the most-traveled vs least traveled segments. ...
0
votes
1answer
647 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
64 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
128 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 ...
2
votes
0answers
148 views

How to find shortest line from a point on a polygon boundary to a multilinestring, but the line is inside polygon (PostGIS)

I have 3 geometries 1 polygon 1 point on boundary 1 multilinestring In this image you can see the problem. I need to find shortest line from point (green square) to line (red), but the line must be ...
2
votes
1answer
97 views

pgr_ksp() returns other columns from edge table

I'm willing to optimise my queries to make it much faster. In my Edge table, I have different information for each edges (distance, speed, duration, ...). The problem is so far my pgr_ksp() function ...
0
votes
1answer
39 views

Using Near_analysis under loop

for i in range (1,7): layer="s"+str(i) arcpy.Near_analysis(layer,"Wall") I have 6 layers labelled s1 to s6 representing 6 points. I'm using Near_analysis to calculate shortest distance of the points ...