# Questions tagged [dijkstras-algorithm]

The tag has no usage guidance.

29 questions
Filter by
Sorted by
Tagged with
1answer
30 views

### UCS and Dijkstra's algorithm do both of them give the minimal cost between two vertices?

i tried both algorithm to find the shortest path with minimal cost between two vertices,but most of the time Dijkstra gives a different path and the cost is smaller than the cost for the path UCS ...
0answers
28 views

### How to modify the following Dijkstra/ Uniform-cost search to return the result for all end points?

I know there is a lot of code out there that does this, but in particular, I'm trying to modify the following code to not just return the goal node/ one end point, but all endpoints. How do I go about ...
0answers
12 views

### Asymptotic growth rate - Dijkstra [closed]

Recall that Dijkstra’s algorithm, using a priority queue, does n Extract-Min operations and at most m Decrease-Key operations. In a d-ary heap (d-heap) with at most n items, the number of comparisons ...
0answers
35 views

### Which heap to use when implementing Dijkstra's algorithm

Dijkstra's algorithm employs a heap. For which $m$ (as a function of $n$) can we choose $d$ so that $d$-heaps outperform Fibonacci heaps? Here $n$ is the number of vertices, $m$ is the number of edges,...
1answer
210 views

### find shortest paths from source to all vertices using Dijkstra’s Algorithm?

For Dijkstra’s,i can find shortest paths from source to all vertices in the given graph but how can i calling the algorithm |V| times taking each vertex as a source and store all tables ??? For ...
2answers
331 views

### CLRS Exercise 24.3-4 - Confirm Output of a Program Claiming to Implement Dijkstra's Algorithm

I'm trying to better understand Question 24.3-4 From CLRS below: Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm. The program produces $v.d$ and $v.\pi$ for ...
1answer
495 views

### Dijkstra without decrease key

I was reading through this paper, "Priority Queues and Dijkstra's Algorithm" by Mo Chen et al., which suggests using Dijkstra's without edge relaxation, but to rather to just insert new ...
2answers
123 views

### Minimum distance in an undirected weighted graph to cover k nodes using teleportations

I have been practicing problems on graphs and shortest paths and I encountered a problem that I'm struggling to understand. Can you give me any tips and/or can you confirm that I got the general ...
1answer
35 views

### shortest path in color-weighted graphs

I want to find an algorithm to find the shortest path in a vertex-colored vertex-weighted graph. Every vertex with the same color has the same weight and the total weight of a path should be the sum ...
1answer
499 views

### Why is DFS not suited for shortest path problem?

I am sorry for the repetition of the question. I understand that this question has already been answered before by the community, but most answers tend to focus on unweighted graphs. I want to know ...
0answers
42 views

### Solving shortest path problem with Dijkstra’s algorithm for n negative-weight edges and no negative-weight cycle

Although many texts state Dijkstra's algorithm does not work for negative-weight edges, the modification of Dijkstra's algorithm can. Here is the algorithm to solve a single negative-weight edge ...
0answers
36 views

### Fastest Algorithm for finding All Pairs Shortest Paths on Sparse Non-Negative Graph

As discussed here Johnson's Algorithm can be used to solve the APSP-Problem in $O(V^2\log V + VE)$ in stead of $O(V^3)$ for Floyd-Warshall. However, Johnsons Algorithm does quite a bit of work for the ...
0answers
73 views

### Find every path that passes through certain edges

I'm faced with the following problem: Given Directed and unweighted graph, where each edge E has two attributes Goal Find every path through the 3 (or more) given edges in a specific order ...
0answers
13 views

### Trivial clarification with the analysis of the Dijkstra Algorithm as dealt with in Keneth Rosen's “Discrete Mathematics and its Application”

I was going through the text, "Discrete Mathematics and its Application" by Kenneth Rosen where I came across the analysis of the Dijkstra Algorithm and felt that the values at some places ...
1answer
207 views

### Create an algorithm for computing the shortest path in O(m + nlogn)

So I'm trying to write an algorithm for computing the shortest path with constraints on the vertices you can visit in $O(m + n \log n)$ time. In this problem, we are given an indirect weighted (non ...
0answers
34 views

### Algorithm to calculate shortest path when updating the heaviest edge in a path [duplicate]

For a given graph $G=(V,E)$ and path $p= v_1 \to v_2 \to ...\to v_k$, $w^\ast(p)$ represents the weight of the path between $v_1$ and $v_k$ excluding max_edge. w^\ast(p) = \sum_{i=1}^{k-1} w(v_i, v_{...
1answer
149 views

2answers
579 views

### Dijkstra and A* Algorithms: Why is A* faster?

I am learning about Dijkstra's Algorithm and the A* Algorithm and I have manually worked through the graph attached here, which is supposed (I think) to demonstrate that the A* Algorithm is faster ...
2answers
226 views

### Why doesn't Dijkstra's use a shortest-path first search?

When using BFS search on an unweighted graph to find the single-source shortest paths, no relaxation step is required because a breadth-first search guarantees that when we first make it to a node, we ...