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
Filter by
Sorted by
Tagged with
2 votes
2 answers
1k views

Dijkstra's algorithm when two edges have same weight

I use Dijkstra's algorithm to find the shortest path from vertex A to vertex D. But edges AB and AC have the same weight. How does Dijkstra's algorithm work if a graph has some same weight edges?
Tom's user avatar
  • 33
1 vote
1 answer
113 views

Why is this Dijkstra not working on directed graph

This dijkstra code isn't working for Directed graphs For example for this testcase: 4 2 1 7 1 2 1 1 3 1 2 1 1 2 4 1 3 1 1 3 4 1 4 3 1 Click to view Graph diagram for above testcase Edge 2 -> 4 ...
Harsh Sharma's user avatar
0 votes
1 answer
331 views

Why Dijkstra worst time complexity is worse using priority queue compared without using it?

I know the sequence of step of Dijkstra algorithm is like these: Initialize arr min_distance, put source as 0, and the others as MAX_VALUE Pick the min distance that's not in visited set Put vertex ...
ktvktv's user avatar
  • 143
2 votes
2 answers
715 views

Dijkstra's shortest path algorithm on directed tree with negative weight edges

Will Dijkstra's shortest path algorithm return correct results on a directed tree with negative weight edges? On a general graph with negative weights, the algorithm will fail, but since it’s a ...
Meir's user avatar
  • 21
2 votes
1 answer
372 views

Whyt is the space complexity of Dijkstra with heap O(V) instead of (V + E)?

About Dijkstra with min heap(priority queue),,, import heapq graph = [ [(1, 5), (2, 3)], [(3, 3), (2, 2)], [(4, 4), (5, 2), (3, 7)], [(4, 1)], [], [(4, 5)] ] v = len(graph) dist = [math....
user19246061's user avatar
2 votes
1 answer
465 views

How to find 2 vertex-disjoint paths in a graph with both paths having same source but different destination?

Let's consider this graph: Let's say I want first path with source as A, destination as H and I want second path with source as A, destination as D. I am not able to apply suurballe algorithm as it ...
SSShet's user avatar
  • 77
0 votes
0 answers
133 views

Memory Limit exceedeed. For the Dijkstra algorithm based on the binary heap

trying to implement a Dijkstra algorithm for my homework. Faced the "Memory Limit exceedeed" error. Please tell me what I'm doing wrong. Memory limit: 8 Mb Statement You are to write a ...
Eva Mask's user avatar
0 votes
1 answer
88 views

How to find the best fit path

I have a set X of ordered weightings e.g. [2, 8, 5, 13, 1]. I am given a graph with edges of various weights. Example graph Given a start node, which algorithm should be used to find the path such ...
Louie Holbrook's user avatar
2 votes
0 answers
133 views

BFS on weighted directed graph

Somehow, my modified BFS is performing better than Dijkstra's? I want to know what the exact time complexity is of this solution, I have spent a lot of time thinking but my only understanding is that ...
Sung Jinwoo's user avatar
1 vote
1 answer
96 views

Dijkstra's: Where is the equation from? m < n^2/log n

In this passage from my textbook: where are the inequalities from? (The ones that I've marked with red rectangles.) I feel that they describe a relationship between vertices and edges in a graph, but ...
hola_mundo's user avatar
2 votes
1 answer
52 views

Djisktra algo implementation returning array of all same values

This is a solution to city problem, where cities have at most 1 train station and 1 bus station, some cities have both. and from a starting city i will be finding all the shortest paths to other ...
C.Unbay's user avatar
  • 2,763
1 vote
1 answer
175 views

Dijkstra's full algorithm using BFS and dictionary bug

Using dictionaries, graphs, and lists, I'm attempting to implement the Dijkstra algorithm with BFS in Clojure. The issue is that I can't get it to work correctly; it won't work when I ask it to return ...
Daniel Shutov's user avatar
2 votes
1 answer
225 views

How does boost graph dijkstra_shortest_paths pick the shortest path when there are multiple shortest paths between a specific pair of nodes?

I have an unweighted, undirected network of around 50000 nodes, from this network I need to extract the shortest path between any pair of nodes. I used the dijkstra_shortest_paths function from the ...
learner_lyf's user avatar
0 votes
1 answer
167 views

Dijkstra Algorithm's source node and graph for grid problem

My grid Im trying to implement Dijkstra algorithm for grid-like graph attached above to find shortest path from source node to every other node. Having watched many tutorials I fail to understand how ...
Shedrah's user avatar
0 votes
1 answer
243 views

Codewars:Path Finder #3: the Alpinist in C++

I just tried to finish a problem:Path Finder #3: the Alpinist in Codewars. I had passed all basic test cases and there were any errors under my own test cases. But when i submited my solution, my code ...
echo's user avatar
  • 86
-1 votes
1 answer
360 views

Dijkstra's algorithm for finding the midpoint with the shortest total route

I need an algorithm to select the midpoint that has the shortest route between the source node s and the destination node h. There are midpoints (intermediate vertices) b in the set of intermediate ...
bloomsdayforever's user avatar
0 votes
1 answer
2k views

TypeError: expected str, bytes or os.PathLike object, not int. In python, when I add some inputs and some function have to use it

Im new at coding and I'm doing a code for algorithms with a request matrix. I'm seeing this error when I add the code with the ***. Context: I'm doing an input menu with options so the user can with ...
toborrm's user avatar
  • 25
1 vote
0 answers
144 views

Algorithm - Find locations close/nearby to a given route

My problem is somewhat similar to Dijkstra's shortest paths algorithm but I am not sure if it's suitable for my case. So, I 'm going to explain this with an example. Let's say we have a shipping ...
nteath's user avatar
  • 250
0 votes
1 answer
968 views

Shortest paths between vertices in two sets

You're given a directed weighted graph, which has m edges and n vertices. Every edge's weight is nonnegative. The vertices are either in set S1 or in set S2 (S1 and S2 are disjoint). You need to find ...
Skyer Walkery's user avatar
1 vote
1 answer
454 views

how do you represent obstacles in a grid for pathfinding as a graph

my program compares A* pathfinding algorithm to dijkstra's algorithm showing how informed searches are better than uninformed. in the write up i explained how a grid is actually a graph with equal ...
Xray25's user avatar
  • 123
0 votes
0 answers
23 views

Path contains mininal heavy weight from s to t

I need to write an algorithm that find a path from s to t by the following condition: we compare bewteen each heaviest edge of each path and choose the path with the lightest edge among the heaviest ...
Programer's user avatar
0 votes
2 answers
528 views

implementing dijkstra's algorithm using a priority queue

So I'm trying to implement Dijkstra's algorithm. I understand Dijkstra's works, but I struggle to turn the concept into code. I have what I thought would be the correct code, I'm getting an out-of-...
student's user avatar
0 votes
0 answers
451 views

Create a weights adjacency matrix in python with networkX

I want to implement the Dijkstra algorithm in python but with weighted adjacency matrix but NetworkX give us just the adjacency without the weights ( distance for my algorithm ) so I tried to search a ...
TechCode's user avatar
1 vote
1 answer
312 views

Shortest path passing through at least 1 node from a subset of nodes

I want to implement a python function that generates the shortest path from a source node to a destination node in a directed, weighted graph. It has to include at least one node from a subset of ...
Archipelago2000's user avatar
0 votes
0 answers
120 views

Dijkstra [with weight] periodically printing forward and reverse path for Directed Graph

I am implementing dijkstra with weight for directed graph :- path=nx.dijkstra_path(G, 1, 4, weight='weight') When I print computed path it shows following:- Computed weighted dijkstra path is: [1, 2, ...
CobaltRed's user avatar
1 vote
1 answer
3k views

Performance improvement for Dijkstra algorithm using heaps in python?

Below is my implementation for Dijkstra's algorithm using heaps (for undirected graphs). This works just fine for reasonably sized graphs however I am not satisfied by my code for recalculating greedy ...
tim_76's user avatar
  • 74
0 votes
2 answers
584 views

Bellman-Ford vs. Dijkstra graph density

I was testing the two algorithms and Bellman-Ford performed better on sparse graphs and looking at the big-O analysis of both, O(VE) for Bellman-Ford and O(E + V lg V) for Dijkstra's. I believe this ...
csstudent3423's user avatar
0 votes
0 answers
47 views

Python Temperamentally Accessing Global Object from within a Function (which references that object from within another)

(Edit: Fundamentally my problem is that python is sometimes creating new instances of an object x,which I accessed by another object y, accessed by z instead of editing the original x directly. x and ...
Hermit's user avatar
  • 35
1 vote
1 answer
63 views

Printing Dijkstra SSSP with recursion and in reverse order

I'm trying to print out the SSSP in a specific order but I'm stucked. lets say I have 2 array: node = [0, 1, 2, 3] pred = [-1, 2, 0, 1] This is the code I've come up with: void printPath (int ...
dtrinh's user avatar
  • 69
0 votes
0 answers
168 views

Why does inconsistent hueristic cause expansion of repeated nodes in A*?

I am aware that we need to follow the triangle inequality for consistent heuristic I.e, h(n)< c(n,a,n')+ h(n') My understanding of why it might cause repeated nodes to be expanded is that , suppose ...
Aditi's user avatar
  • 147
0 votes
1 answer
237 views

Display nodes from the shortest path between two nodes

Let's say that we use Dijkstra algorithm and now we know the shortest distance between source node and every node from the graph. What should I do to know which nodes was visited for every distance?
Stănescu Cristian's user avatar
0 votes
0 answers
729 views

application of Dijkstra’s shortest path algorithm

I am applying Dijkstra’s shortest path algorithm, it works well with another examples, but I could not figure out why it does not give me the correct result for my example below . Please give any help ...
Albert G Lieu's user avatar
-1 votes
1 answer
198 views

how to add infinity to all values in the path for a* algorithm

I am following this pseudocode trying find the best path from a maze using a* algorithm in python. The maze will be something like this. It's a 2d array you can only navigate in the zeros the x are ...
studentpr's user avatar
0 votes
1 answer
122 views

Djikstra's algorithm with change in cost function

I am facing the following coding challenge question: "You are at start location [0, 0] in mountain area of NxN and you can only move in one of the four cardinal directions (i.e. North, East, ...
Joachim's user avatar
  • 500
0 votes
0 answers
41 views

Is this vector 2d struct calling right?

I try to use struct into a vector 2d like this: struct Node { int x; int y; int ts; }; vector <Node> adj[5000][15]; And create a dijkstra function like : void dijkstra(int x1, int x2) { ......
ClickW's user avatar
  • 11
1 vote
0 answers
42 views

TreeSet wont add edges

i have to code the Dijkstra algorithm. We got a blueprint for this project. Meaning we were told the classes, field variables and methods we have to use. We have to read the adjacency matrix from a ...
Sero619's user avatar
  • 11
0 votes
0 answers
47 views

Which point makes difference of execution speed in JS?

im studying Algorithm with Javascript. It is a problem abt dijkstra algorith. but i always meet TLE(Time Limit Exceeded) in the last case. could i know which point makes my code slower. i tried many ...
KangHyun Lee's user avatar
2 votes
2 answers
222 views

In SPFA Shortest Path Faster Algorithm why does it have to check if current vertex is in queue before adding it to queue?

procedure Shortest-Path-Faster-Algorithm(G, s) 1 for each vertex v ≠ s in V(G) 2 d(v) := ∞ 3 d(s) := 0 4 push s into Q 5 while Q is not empty do 6 u := poll Q 7 ...
Focus's user avatar
  • 974
2 votes
1 answer
202 views

Throw an error if multiple shortest paths are found

Given an undirected weighted graph, a start, and an end point. You need to find the shortest path to that end point, but throw an error if multiple shortest paths are found. How would we do the error ...
Abhimanyue Singh Tanwar's user avatar
-1 votes
1 answer
87 views

Dictionary Key as object returning KeyNotFoundError

I am trying to implement Dijkstras path finding algorithm in Unity. I have a dictionary distances containing all the possible Nodes that can be walked on which is obtained from GridData.WalkableNodes....
Krellex's user avatar
  • 649
0 votes
0 answers
11 views

Dijkstra's Algorithm for simchi-levi berman's network

Does anyone have the shortest paths for this network? enter image description here
Lora Allen's user avatar
0 votes
1 answer
172 views

Memory Usage for Dijkstra's Algorithm in Haskell

I've been learning Haskell as I find the language to be expressive, and to practice it, a friend has been giving me problems from Codeforces to do. The current problem I've been working on is to ...
MIlkywayw's user avatar
2 votes
1 answer
375 views

CSP Finding Path

I am able to implement the default uniform cost search (python) to find the shortest path between two nodes (path cost). I followed this pseudocode:
fapiyas739's user avatar
0 votes
1 answer
66 views

How does ` igraph` calculate the shortest path in a weighted directed network, using Dijkstra's Algorithm?

I would like to calculate the betweenness of a network like e.g. >dput(relations) structure(list(From = c("France", "Italy", "Malta", "Spain", "Germany&...
Mark's user avatar
  • 1,663
2 votes
1 answer
222 views

Shortest Path with Dijkstra’s Algorithm from a dataframe

I am trying to find shortest path between graph nodes using Dijkstra's Algorithm, by using the code enclosed in the following article: https://www.r-bloggers.com/2020/10/finding-the-shortest-path-with-...
Mark's user avatar
  • 1,663
1 vote
1 answer
845 views

How can I find shortest path with maximum number of yellow edges

In given directed graph G=(V,E) , and weight function: w: E -> ℝ+ , such any vertex with color yellow or black, and vertex s. How can I find shortest path with maximum number of yellow edges? I ...
StudentOrint's user avatar
-1 votes
1 answer
97 views

How to use always the same type of edge in a directed weighted graph?

I'm doing a project for college and we are simulating a public transport (Only bus) system using directed weighted graphs in c++. Each node represents a stop and each edge represents the line of the ...
Eduardo Silva's user avatar
0 votes
0 answers
162 views

Algorithm to detect best path in a multigraph

essentially I have a multigraph where each edge has its own identity and the weight of each edge is dependent upon some starting input. I have created a dijkstra-based search algorithm that can detect ...
getJiggy's user avatar
0 votes
1 answer
32 views

Returning a value from a function failed with NoneType [duplicate]

I have a problem with returning a value from an external function. Function: def dijkstra(netzwerk,startpunkt,zielpunkt,punkt_geprueft=[],entfernungen={},vorgaenger={}): if startpunkt not in ...
ähmöhm's user avatar

1 2 3
4
5
39