# 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 ...
• 11.6k
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 ...
• 39k
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 ...
• 620
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 ...
• 2,063
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 ...
• 1,095

### 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 ...
• 6,202

### 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 ...
• 6,202

### 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 ...
• 8,303

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

• 6,202

### Disconnection of a directed and weighted graph

The algorithm is not correct. Imagine the following graph: ...
• 16.7k

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

### 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 ...
• 39k

### 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 ...
• 16.7k

### 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 ...
• 162k

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

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

### 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,142
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 ...
• 6,202

### 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 ...
• 29.5k
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 ...
• 39k
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 ...
• 39k
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, ...
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 ...