Questions tagged [dijkstra]
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra is a graph search algorithm that solves the single-source shortest path problem for a connected graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms.
dijkstra
1,926
questions
2
votes
1
answer
81
views
Modified Dijkstra - Time Complexity?
I am solving the Leetcode Problem 787. Cheapest Flights Within K Stops.
Basically this is single source shortest path, but with max k steps allowed. So, we can't use normal Dijkstra algorithm, where ...
- 59
1
vote
1
answer
84
views
Dijkstra's algorithm vs Viterbi algorithm
Viterbi and Dijkstra's algorithm seem to be used in different contexts:
Viterbi algorithm is usually employed to solve maximum likelihood sequence problems (I've used for this purpose in ...
- 151
0
votes
0
answers
20
views
Parallel implementation of Dijkstra: problem scaling with constant efficiency
I am learning about parallelization, but I am stuck on this problem: assume that you achieve a parallel efficiency of 70% for computing the shortest path for a graph with n = 20000 vertices on 16 ...
- 83
0
votes
0
answers
29
views
Using geojson file I want to create a navigation system and find shortest path and draw a line
I have a Geojson file with road network. Now what I want is to create a navigation system using this geojson file. I draw the road network using Leaflet js. now I need help to apply dijgsta algorithm ...
0
votes
1
answer
47
views
Bellman-Ford with Adjacency List (Shortest-path with negative weights)
I'm implementing my own version of the Bellman-Ford algorithm to find shortest paths with negative weights. However I'm not sure if this is correct, since in my opinion the complexity in my solution ...
- 343
0
votes
0
answers
17
views
Refinement of the launch function of the Dijkstra algorithm
The elements of the following dictionary are used as input:
nodes = {"Склад": (43.356374, 132.072318), "Некрасовская": (43.128128, 131.910649), "3-я Рабочая": (43.123089, ...
0
votes
1
answer
104
views
Graph shortest path Dijkstra - time optimisation
So im proceeding through my Algorithm course
Input data
The first line of the input data contains two numbers: 𝑛 (2≤𝑛≤2⋅10^5) and 𝑚 (1≤𝑚≤4⋅10^5) — the number of settlements in the empire and the ...
- 19
0
votes
0
answers
20
views
RDD lookup operation performing weirdly
I'm currently exploring PySpark and attempting to implement Dijkstra's algorithm using it. However, my query doesn't pertain to the algorithm itself; it's regarding the unexpected behavior of the ...
0
votes
2
answers
67
views
Find shortest path between two nodes, all paths are equal to one
Is Dijkstra's algorithm the most suitable for finding the shortest distance between two nodes, where all of the paths in the graph are equal to 1.
If not what is a more time efficient way of ...
0
votes
1
answer
19
views
Is there an algorithm for turning a pixelated path into a set of vectors and curves?
I have made a pathfinding program for my robotics team, and it uses Dijkstra's Algorithm (will change to A* eventually) to get the fastest path between two points. It outputs a list of points in the ...
- 1
0
votes
0
answers
52
views
Refrence to "..." is ambiguous [duplicate]
I am trying to implement Dijkstra's algorithm to solve a problem for school, but I keep getting the error "Reference to distance is ambiguous".
Here is my code:
#include <bits/stdc++.h>...
0
votes
1
answer
39
views
How to limit the number of paths in Dijkstra algorithm in Neo4j
I hope that when using Dijkstra algorithm, the shortest path does not exceed 4 nodes. means with condition of both path's weight and path's num for cypher。
This is my drawing neo4j command:
CREATE (c:...
0
votes
0
answers
38
views
Implementing restrictions via multiple links into dijkstra routing algorithm
I have successfully implemented a Dijkstra algorithm for finding optimal routes in road networks. I have constructed the data so that there are no "nodes", instead I use road segments, and ...
- 1,420
0
votes
0
answers
44
views
shortest path algorithm with expected cost
My objective is to calculate the expected cost for each path from the starting point to the end point and identify the minimum expected cost for each path when the respective node serves as the ...
- 159
2
votes
1
answer
97
views
Shortest path finding in grid with turn cost
Stack Overflow community!
I'm working on a pathfinding problem within a 3x3 grid, where each cell has a variable cost based on its coordinates, and there are additional costs for making 90-degree ...
