39
votes
Example of a graph with negative weighed edges in which Dijkstra's algorithm does work
Take a look at the simplest possible example: Our graph has only two nodes: $s,t$, and a single edge between them.
In this example, it won't matter what is the cost of this single edge (it can be ...
- 11.4k
9
votes
Accepted
What role is the set, S playing in Dijkstra's algorithm given in the book CLRS?
No, you are not missing anything if you remove $S$ completely. You could implement and run Dijkstra's algorithm correctly still.
Set $S$ is used later in the book to help explain the algorithm and ...
- 38.2k
7
votes
Accepted
Find the shortest path that goes through an even number of red edges
Here's a nice way to do it. Make two copies of the input graph; call them $A$ and $B$. Now redirect the red edges so that they jump across to the other copy, but leave the blue edges untouched. Any ...
- 575
6
votes
Accepted
How does Dijkstra's problem 1 (tree of minimal total length) work and what does it do?
In modern terms, this problem is called Minimum Spanning Tree: Find the subtree of the input graph that minimizes the total weight of its edges. The algorithm here suggested by Dijkstra is today known ...
- 682
6
votes
Why is my implementation of Dijkstra's Algorithm using min heap faster than using an unsorted array for a complete graph?
It depends on the input graph also. Perhaps, heap.decreaseKey() operation is not happening as frequently as it should. For example, consider a complete graph: $G = (V,E)$ such that all its edge ...
- 4,161
5
votes
How does Dijkstra's problem 1 (tree of minimal total length) work and what does it do?
The tree of minimum total length is nothing but the minimum spanning tree. The algorithm that you are talking about is nothing but Prim's algorithm, also called Prim–Dijkstra algorithm.
Answer to Your ...
- 4,161
5
votes
Accepted
Dijkstra's algorithm vs A*
Yes, that is a common variant. In fact, Dijkstra himself included this early termination in his algorithm (see problem 2). So in that sense it's not really a modification, it's how Dijkstra himself ...
- 1,943
4
votes
Accepted
Modified shortest path problem
Notice that if you allow once jumping without paying the weight cost, then the shortest path is exactly what you need.
Create 2 copies of $G: G_1,G_2$. For every edge $e=(v,u)\in G$ also add an edge $...
- 11.4k
4
votes
Example of a graph with negative weighed edges in which Dijkstra's algorithm does work
Dijkstra's algorithm sometimes works when there are negative weights, and sometimes not, others have given several examples. Allow me to give a few ideas that may make it easier to find an example on ...
- 7,438
4
votes
Example of a graph with negative weighed edges in which Dijkstra's algorithm does work
Yet another way to prove the existence is to take any graph G, and replace one edge E with weight W by two new edges and an intermediate node N. Let the first new edge have weight -W/2 and the other ...
- 839
3
votes
Can you use Dijkstra's algorithm to find the maximum cost path?
No, Dijkstra's algorithm will not work. Consider the following counter-example:
$V = \{s,u,t\}$ and $E = \{(s,u),(u,t)(s,t)\}$. The weights on the edges is as follows: $w(s,u) = 1$, $w(u,t) = 3$, and $...
- 4,161
3
votes
Find the shortest path that goes through an even number of red edges
An alternative (but essentially equivalent to @SamWestrick's) way of thinking about it is to run Dijkstra on the original graph but keeping track of two parameters for each vertex: the shortest path ...
- 251
3
votes
Dijkstra without decrease key
You are right. Checking k < d[u] is not sufficient and updating d[u] on the next line is not necessary.
The check prevents ...
- 419
3
votes
Gas Station Problem - Dijkstra's Algorithm variation
We note that we can assume that the source node has a gas station with refilling cost as $0$, even if it doesn't. It just makes the algorithm cleaner, as we start out with a full tank, and we note ...
- 450
3
votes
Accepted
"Subpaths" of Dijkstra's shortest path also shortest?
Of course, it is true. However, it is not a property of Dijkstra's algorithm but is property of the shortest paths themselves. Suppose that is not true, and you have a shorter path from $C$ to $B$, we ...
- 687
2
votes
Dijkstra and A* Algorithms: Why is A* faster?
I absolutely don't understand the attached images and what you try to do on it. What I can say is that Dijkstra an A* algorithm are pathfinding methods:
Dijkstra algorithm is an exploration method ...
- 1,728
2
votes
Why doesn't Dijkstra's use a shortest-path first search?
Dijkstra's already does follow the shortest pah found so far to one of the remaining nodes at each step.
I think your confusion lies in the "enqueue each neighbor of the current node" step: we can't ...
2
votes
Accepted
Why doesn't Dijkstra's use a shortest-path first search?
Congratulations! You have discovered an interesting variation of Dijkstra's algorithm.
However, it is misleading to state the standard version of Dijkstra's algorithm (stDA) described here as ...
- 38.2k
2
votes
shortest path in color-weighted graphs
This problem seems to be NP-hard. A reduction from 3-SAT is left as an exercise, but here is a hint. The empty nodes are free, and then create a color for each literal and its negation. The cost is ...
- 14.5k
2
votes
Example of a graph with negative weighed edges in which Dijkstra's algorithm does work
One other setting where Dijkstra will always work is where the only negative edges in the graph are ones leaving the start node $s$ and there are no other edges leaving $s$. The idea is that the ...
- 9,007
2
votes
Find an algorithm which returns the weight of a lightest path between all paths with a weight divided by three
Since you asked for a hint: study the answer to How hard is finding the shortest path in a graph matching a given regular language? and understand it deeply. Then think about how to apply similar ...
D.W.♦
- 152k
2
votes
Algorithm for shorthest path that contains exactly n edges of weight 2 in 1,2-weighted directed graph
When all edges have weight 2 and $n = |V|$ the problem is equivalent to longest path which is NP-complete. So unless P = NP, there is no efficient algorithm for solving the problem.
- 22.4k
2
votes
Dijkstra's algorithm in a weighted graph
In the second graph, we can replace each undirected edge with two directed edges. For example we can replace edge between D,C with a directed edge $D\to C$ and directed edge $C\to D$ such that each ...
- 1,554
2
votes
Accepted
Why is my implementation of Dijkstra's Algorithm using min heap faster than using an unsorted array for a complete graph?
Here is a worst-case example of a complete graph where the heap.decreaseKey() operation executes on every edge:
Let the vertices be $V = \{1,2,\dotsc,n\}$. The edge set $E$ is such that for every ...
- 4,161
2
votes
Shortest path with forced intermediate nodes
The problem you are trying to solve is $\mathsf{NP}$-Hard. In fact, it is hard to even decide whether any such path exists.*
Indeed, let $G=(V,E)$ be your graph and $s,t \in V$ be the start and end ...
- 26.4k
2
votes
Accepted
Dijkstra's Algorithm Same Node Added Multiple Times to Priority Queue
Consider what will happen for the following graph.
counterexample_graph = {
'U': {'V': 6, 'W': 7},
'V': {'X': 10},
'W': {'X': 1},
}
Suppose ...
- 38.2k
2
votes
Accepted
Dijkstra as a greedy algorithm
Yes, instead of the shortest path problem, we should consider the all shortest path problem or, more precisely, single-source shortest-paths (SSSP) problem. For SSSP, given node $s$, the objectives ...
- 38.2k
2
votes
Dijkstra's shortest path algorithm
Dijkstra's algorithm might solve some cases where there are negative edges in the graph. However, it doesn't solve for every graph that has a negative edge. For instance, if you have a negative cycle, ...
- 88
1
vote
Dijkstra's algorithm in a weighted graph
The first graph is a directed graph with no negative cycles.
However, the second graph is an undirected graph that has a negative cycle. This means that there is no shortest path, since we can always ...
- 11.4k
1
vote
Dijkstra's Algorithm Invariant
I believe your proof is a bit incomplete, since you do not guarantee the shortest path to $d$ is a path which only traverses the popped nodes. You can add this part to make you proof complete :
Assume ...
- 72
Only top scored, non community-wiki answers of a minimum length are eligible