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 [dijkstra]

an algorithm (named after its discover, E.W. Dijkstra) solves the problem of finding the shortest path from a point in a graph (the source) to a destination.

0
votes
0answers
23 views

Complex edge conditions on geo-edges

Spatial graph databases are capable to find a shortest path from the node A to the node B. Are there any DB which allows complex conditions on nodes and edges between them? For example: The node is ...
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 ...
1
vote
0answers
40 views

Dijkstra’s graph returns infinite cost in QGIS?

I borrowed some code from the Network analysis library, modified as appropriate. The goal is a program that measures the distance between a location and a train station. Eventually, this will loop ...
1
vote
1answer
33 views

How to write dynamic SQL for a function that has dynamic SQL parameter?

I am trying to execute a string SQL query in function i.e. Create or Replace Function Route(edge_table text) Returns table(sequence integer) as $$ Begin Return Query Execute 'with r as( SELECT seq, ...
1
vote
0answers
99 views

PgRouting queries too slow

I'm writing a function that returns routes using PgRouting (v.2.6) The main problem I'm having is that I cant get the time less than 1 second per query. The main query I need is get time, length, and ...
1
vote
0answers
118 views

How to save shortest path attributes to a new layer with PyQGIS?

I'm using QGIS 2.14.22 Essen. I'm using network analysis dijkstra() to find the shortest path from p1 to p2 on a power grid network. But what i get from it is the shortest path without any attributes ...
0
votes
1answer
100 views

pgr_dijkstra one to many

I´m using pgr_dijkstra one to one and it´s ok, but error occour when I try one to many or many to many. I´m typing: SELECT * FROM pgr_dijkstra('select id, source ,target, cost from edge', ...
2
votes
1answer
192 views

pgrouting no result // topology problem

First of all, I am new to map making, and I am mostly relying on tutorials to learn. As part of a project, I am making an airway map using QGIS and I do it by uploading the points with lat/long thru a ...
0
votes
0answers
37 views

pgr_bdDijkstra id2 column (or edge column) returns null sometimes

I have a trouble with the pgr_bdDijkstra function of pgRouting. Sometimes the output is correct and other times the column id2 return null into all entries, but the column id1 ever is correct, ...
1
vote
2answers
68 views

Selecting lines with start and end points inside polygons but do not cross them with PostGIS

After trying several ways of selecting those lines, I can't seem to find any kind of solution. So, I have two tables network : lines forming a network containing source (id of node) and target (id ...
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
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
532 views

How can I calculate the shortest path between 2 points and insert the line result as a feature in a layer?

I try to make a script to find the shortest path between two bridges in a network. The goal is to get after each calculation a line that I insert as an entity in a predefined layer. For now I do well ...
2
votes
1answer
153 views

How can I insert the result of the dijkstra algorithm as a feature in a table with PyQGIS?

I ask for your help with the PyQGIS API. Being a new user of GIS I would like to carry out an operation. It is for me to look for the shortest path in a graph using the DIJKSTRA algorithm. The code ...
1
vote
0answers
215 views

QGIS Graph Nonetype using Dijkstra's

I am currently using the Dijkstra's algorithm to find the shortest path between multiple latitudes and longitudes on QGIS. Most of my code is from the Dijkstra's documentation here: http://docs.qgis....
1
vote
0answers
146 views

How to convert a coordinates to indice array (vice versa) in a NetworkX graph?

I want to use a raster for a A* and bidirectional Dijkstra path analysis in NetworkX. I am using Python for this project. Raster example (it's a png file converted when uploaded, but the real problem ...
9
votes
0answers
253 views

Executing bidirectional dijkstra on TIFF image?

Can anyone indicate an example of how to do this? Link, tutorial etc... I started a discussion here about how to load a TIFF image like a graph nicely answered by @sehe. But, in this post the image is ...
0
votes
1answer
277 views

Calculate shortest path and distance between multiple OD pairs using pgr_dijkstra one-to-one

My goal is to find the distance and shortest path between 1000+ Origin-Destination pairs in a road network. I have a table with the pair ID, the origin vertex ID and the destination vertex ID for each ...
1
vote
2answers
959 views

How to convert a shapefile into a graph in which use Dijkstra

I am working in a simulation using NetLogo, the idea is to make the agents interact inside the roads of a simplified city, in order to do that I need to use some algorithms to find the fastest path ...
1
vote
1answer
120 views

Syntax of pgr_dijkstraCost()

I am trying to find the shortest path between buildings and any electric plants on a network. The thing is, when I use the following query, I overload my RAM (network_nodes and network_edges each ...
0
votes
0answers
88 views

pgr_dijkstraCost() Many-to-Many exceeding RAM disponibility

I am working with PostGreSQL 9.6, pgRouting 2.4.1 and PostGis 2.3.1 on a Linux with 3Gb of RAM and 4Gb of SWAP. I am trying to launch the following query : SELECT start_vid as building, end_vid as ...
2
votes
0answers
51 views

Routing for specific subjects (cars, pedestrians, ..) dynamically

I need create app which will be provide routing for specific category. For example only for cars, only for bikes or only for pedestrians. For importing OSM data I'll used default mapconfig for all way ...
0
votes
1answer
294 views

pgr_dijkstra function with geometry column in result

can you help me to edit my pgr_dijkstra function to required result? Currently I had this select: SELECT * FROM pgr_dijkstra(' SELECT gid AS id, source, target, cost, ...
1
vote
1answer
635 views

Create shapefile line from a list of point coordinates in a stand-alone python script

I've used pyqgis to calculate the shortest path through a network between two points. I want to turn this shortest path into a polyline. I've managed to use the QGIS dijkstra function to calculate a ...
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
151 views

How to make a pgr_dijkstra wrapper with reverse cost?

I'm trying to prepare a dijkstra wrapper for Geoserver. I got a code from my professor and have to modify it so that it uses the dijkstra algorithm with the reverse cost argument. Can anyone please ...
0
votes
1answer
162 views

QGIS crash when looping through features in network analysis (dijkstra)

My script to compute distance in my network works. Now I want to loop over all features of a point layer to produce multiple distance calculations. Just iterating over the features work of course and ...
0
votes
1answer
646 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 ...
0
votes
0answers
452 views

Problem with pgr_dijkstra query

I'm very new to pgRouting and I'm trying to run a simple query, which is the following: SELECT * FROM pgr_dijkstra('SELECT id, source, target, time AS cost FROM road_network_noded', 1000, 757, false)...
0
votes
0answers
427 views

Displaying Dijkstra's result as a path in a map

I have implemented a Java Program that asks for two points X and Y and then run Dijkstra algorithm to find the shortest path from X to Y. The returned path is represented as a sequence of nodes each ...
0
votes
2answers
283 views

Shortest path problem from A to B on routing engines

I am in the process of creating a routing engine. I have encountered the following problem. Lets say the user gives a point A and point B and expects to get the A->B shortest path. I am using simple ...
0
votes
1answer
561 views

How to implement Shortest Path in Openlayers 3 and Geoserver 2.8.2?

I've managed to get all the SQL queries necessary to get the shortest path with Dijkstra using pgRouting, but now I want to implement them in my website using OpenLayers 3 and GeoServer 2.8.2 The ...
2
votes
2answers
941 views

How does pgr_createTopology assign source and target?

This is the first time I post a question here. I was following the tutorial from Anita Graser http://anitagraser.com/2013/07/06/pgrouting-2-0-for-windows-quick-guide/ , on a roads table which ...
1
vote
0answers
100 views

Dynamically updating path weights with route in ModelBuilder?

I am trying to force the routing to reuse as many path parts as possible as described in initial question. The submodel for it is as follows: What it supposed to do is as follows: The path from the ...
1
vote
1answer
94 views

Force closest facilities take the same route

I have a routing problem that I intend to solve with ArcGIS network analyst. First, Closest facility works perfect for me to find the shortest paths to a number of demands. The results look like the ...
1
vote
0answers
300 views

Dijkstra's Algorithm direction issue [closed]

I am trying to implement Dijkstra's algorithm, my query is working fine if I set direction parameter to false. I have to consider the direction of travel while calculating route from point A to point ...
1
vote
0answers
101 views

QGIS : strange tiedpoints after makeGraph

I try to use the Dijkstra shortest length path calculation. On the following program, when I use the Network.shp file (found here : https://geospatialpython.googlecode.com/svn/network.zip) with ...
-1
votes
1answer
480 views

Pedestrian routing using pgRouting

I'm new to pgRouting and I want to implement a pedestrian routing system. I've already implemented a routing system using pgRouting, PostGIS, GeoServer, OSM data and OpenLayers 3 and it uses Dijkstra ...
0
votes
0answers
42 views

Pgrouting (QGIS) multiple point [duplicate]

I have read al lot of the pgrouting, but i still not quite sure if it can do what i want. I have 20 stop points and i have 1 starting point and 1 finish point. I want to calculate the shortest path ...
1
vote
1answer
382 views

Repair topology before pgrouting / No results of pgrouting

My goal is to calculate lots of distances along the streets. I followed http://workshop.pgrouting.org/ tutorial except that I used osm2po instead of osm2pgrouting to import osm file. The only problem ...
1
vote
1answer
1k views

Calculating shortest path between each lat/lon point in one table and each lan/lon point in another in PostgreSQL?

I have two tables, both of them have only 2 columns. The first one contain only latitude and longitude coordinates of my source points and the other one only latitude and longitude coordinates of my ...
1
vote
1answer
285 views

How to implement stopovers in pgrouting?

I used to use Dijkstra to find the shortest path between two points. Now I have a shortest route, which uses a street forbidden to use because of internal rules (too slow due to shopping mall). Now ...
5
votes
4answers
2k views

Using python QGis network analysis library to calculate short path based on speed and distance?

I want to calculate and show short path from starting point to an end point in a qgis python plugin. in my research i stopped by an article about QGis network analysis library; http://www.qgis.org/en/...
4
votes
1answer
900 views

pgRouting 2.0 slow execution of A star algorithm [closed]

Recently, I wanted to test pgRouting ver. 2.0. I created the database structure with osm2po and imported UK map from geofabrik. The data was imported correctly. When I execute a sample query in ...
2
votes
0answers
215 views

dijkstra_sp_directed not returning any result

I am trying to create a routing application with OSM data. What I am working with is an almost square area of about 30x30 kilometers, so nothing too big. But when I do something like SELECT ...