# Tag Info

### 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 ...
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 ...
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 ...
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 ...

### 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 ...

### 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 ...
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 ...
Accepted

### 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 ...

### 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 ...

### 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 ...
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 ...

### 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 ...

### 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 ...
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 ...

### 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 ...

### 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 ...

### 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 ...

### 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.

### 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 ...
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 ...

### 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 ...
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 ...
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 ...

### 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, ...
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 ...
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 ...

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