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 ...
nir shahar's user avatar
  • 11.5k
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 ...
John L.'s user avatar
  • 39k
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 ...
Sam Westrick's user avatar
6 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 ...
harold's user avatar
  • 2,053
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 ...
Highheath's user avatar
  • 1,046
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 ...
Inuyasha Yagami's user avatar
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 ...
Inuyasha Yagami's user avatar
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 ...
Discrete lizard's user avatar
  • 8,248
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 ...
MSalters's user avatar
  • 895
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 $...
nir shahar's user avatar
  • 11.5k
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 ...
Especially Lime's user avatar
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 ...
Ryoji's user avatar
  • 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 ...
CodeChef's user avatar
  • 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 ...
Vladislav's user avatar
  • 687
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 $...
Inuyasha Yagami's user avatar
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 ...
Optidad's user avatar
  • 1,788
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 ...
BlueRaja - Danny Pflughoeft's user avatar
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 ...
John L.'s user avatar
  • 39k
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 ...
Pål GD's user avatar
  • 16.1k
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.'s user avatar
  • 159k
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.
Juho's user avatar
  • 22.6k
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 ...
ErroR's user avatar
  • 1,910
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 ...
templatetypedef's user avatar
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 ...
Inuyasha Yagami's user avatar
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 ...
Steven's user avatar
  • 29.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 ...
John L.'s user avatar
  • 39k
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 ...
John L.'s user avatar
  • 39k
2 votes

Single Source Shortest Path Problem with Multiple Weights Each Edge

You can use the following variant of the Floyd-Warshall algorithm: Let $u$ and $v$ be any vertices in the graph. Let $E_u$ and $E_v$ be the set of edges incident on $u$ and $v$, respectively. Then, ...
Inuyasha Yagami's user avatar
2 votes

Single Source Shortest Path Problem with Multiple Weights Each Edge

Let $G=(V,E)$ be the original graph. Define a new graph, $G'=(V',E')$, that represents the set of all valid paths in $G$, where a path is considered valid if its $q$-values are strictly monotonically ...
D.W.'s user avatar
  • 159k
2 votes

Disconnection of a directed and weighted graph

The algorithm is not correct. Imagine the following graph: ...
Pål GD's user avatar
  • 16.1k

Only top scored, non community-wiki answers of a minimum length are eligible