Questions Tagged With dijkstrahttps://help.openstreetmap.org/tags/dijkstra/?type=rssquestions tagged <span class="tag">dijkstra</span>enFri, 04 Mar 2022 13:30:22 +0000convert the OpenStreetMap database to a weighted graphhttps://help.openstreetmap.org/questions/83640/convert-the-openstreetmap-database-to-a-weighted-graph<p>Trying to convert the OpenStreetMap database to a weighted graph in order to apply algorithms like Dijkstra or A*.
Any ideas on how to make the algorithm working on the data? The thing is to convert all the database in one time and then apply the algorithm.
Right now I'm thinking of just read the database and extract the information needed to construct the graph. Make the roads as edges. As for the nodes, it's hard to determine what kind of location to keep.
Need help :)</p>wothellFri, 04 Mar 2022 13:30:22 +0000https://help.openstreetmap.org/questions/83640/convert-the-openstreetmap-database-to-a-weighted-graphgraphdijkstraosmconvertdatabaseHow convert a street map(.osm or .shp) into a weighted graph with major street squares as node and length of the street between these nodes as weight?https://help.openstreetmap.org/questions/78340/how-convert-a-street-maposm-or-shp-into-a-weighted-graph-with-major-street-squares-as-node-and-length-of-the-street-between-these-nodes-as-weight<p>To apply algorithms like Dijkstra on a graph, we need nodes and the distance between each node as weights. In real world these weighted graphs are actual maps and the weights are distance of road. We are looking for a library or a tool which we can be used to convert these map files(.shp or .osm) into a weighted graph or an adjacency matix? </p>KartikeyaWed, 13 Jan 2021 06:27:51 +0000https://help.openstreetmap.org/questions/78340/how-convert-a-street-maposm-or-shp-into-a-weighted-graph-with-major-street-squares-as-node-and-length-of-the-street-between-these-nodes-as-weightmaptographdijkstraroaddistancestreetdistancedistancedisplaying Dijkstra result as a route in real maphttps://help.openstreetmap.org/questions/50283/displaying-dijkstra-result-as-a-route-in-real-map<p>So I got the result of Dijkstra as sequence of coordinates</p>
<pre><code>lat_1,lon_1
lat_2,lon_2
....
....
lat_n,lon_n
</code></pre>
<p>where lat_1,lon_1 is the start point and lat_n,lon_n is the end point of the vehicle route. I need to display this path on real map. After adding node_id and description, I used GPSVisluazer website to create GPX file. I opened it in jpeg and Google Map and all show just set of points or markers with no connected lines between them. Now my question is: how to display the result of Dijkstra on OSM or at least having it as image? I checked rendering and routing sections in openstreetmap.org but there is nothing obvious. </p>xlineFri, 17 Jun 2016 12:50:19 +0100https://help.openstreetmap.org/questions/50283/displaying-dijkstra-result-as-a-route-in-real-mapdijkstraosmdisplayShortest path problem from A to B on routing engineshttps://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-engines<p>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 Dijkstra for now.</p>
<p>Let's say that I can somehow find the <code>(latitudeA, longitudeA)</code> and <code>(latitudeB, longitudeB)</code> coordinates, which are the closest coordinates to the A and B points that the user inputted. From those coordinates I could then also find the <code>nodeA_ID</code> and <code>nodeB_ID</code> on the graph. The problem is that for those nodes it is very likely that the A->B path doesn't exist at all. For example, if node A was only part of a one-way road that went to the opposite direction that the user wanted to go to.</p>
<p>However, a <strong>A'</strong> and <strong>B'</strong> must exist, <em>very close</em> to A and B respectively, so that the <strong>A'->B'</strong> path exists. So the routing engine should try and find that <strong>A'->B'</strong> path instead.</p>
<p>Also, that <strong>A'->B'</strong> path might not even be <strong>optimal</strong>. There could have been a <strong>A''->B''</strong> path, where A'' and B'' were only a couple of meters away from A and B. So the routing engine should find the <strong>A''->B''</strong> optimal path instead.</p>
<p>How do routing engines handle this situation ? </p>shiro900Fri, 08 Apr 2016 19:07:08 +0100https://help.openstreetmap.org/questions/49117/shortest-path-problem-from-a-to-b-on-routing-enginesenginepathdijkstraroutingshortestHow to route origin to destination using only OSM data?https://help.openstreetmap.org/questions/30843/how-to-route-origin-to-destination-using-only-osm-data<p>Hi,
Using a ready made open source API is not an option. All I have to work with is filtered OSM data consisting of only nodes of roads and ways.</p>
<p>Can somebody please give me some insight regarding how I can draw a route from an origin to a destination node?</p>
<p>I'm struggling to see how routing algorithms such as Dijkstra or A* fit in with nodes & ways.</p>
<p>Any help would be appreciated.</p>
<p>Thanks</p>KyaniteWed, 19 Feb 2014 18:03:49 +0000https://help.openstreetmap.org/questions/30843/how-to-route-origin-to-destination-using-only-osm-datawaysnodesdijkstraosmroutingHow to use Djikstra's Algorithm on Android with OSM?https://help.openstreetmap.org/questions/19480/how-to-use-djikstras-algorithm-on-android-with-osm<p>I have a task form my lecturer.
I have to make a routing application that must use <strong>Dijkstra's Algorithm</strong> as the Shortest Path Algorithm.</p>
<p>So far, I've done put the OSM map on my app, but I don't know how to put this dijkstra's algorithm on my app.</p>
<p>The thing that I know, i have to know the graph first and the value of each line. So, i can use the algorithm. </p>
<p><strong>How to convert OSM map to the graph and know the value?
Can anybody help me how to this or have better method?</strong>
Thanks.</p>rizkydpThu, 31 Jan 2013 06:32:35 +0000https://help.openstreetmap.org/questions/19480/how-to-use-djikstras-algorithm-on-android-with-osmandroiddijkstra