# Tag Info

39

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 negative), and Djikstra will always return the only single path between $s$ and $t$: which is directly $s\rightarrow t$.

7

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 path which starts and ends in $A$ must use an even number of red edges (after using a red edge to get to $B$, it has to use another red edge to get back to $A$). ...

7

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 as Prim's algorithm. Regarding your question, the "corresponding branch" to a node $b$ in set $B$ is the shortest edge that runs from some node that ...

6

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 weights are $1$. In this case, the heap implementation will work faster since distance[v] for every vertex will be set to $1$ in the first iteration. The heap....

5

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 Question: The corresponding branch is defined for every vertex $v \in B$. It is the minimum weighted edge among the edges that are incident on $v$ and set $A$. ...

5

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 described the algorithm to begin with. As Wikipedia puts it: Dijkstra's original algorithm found the shortest path between two given nodes, but a more common ...

4

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 $(v_1,u_2)$ between the node $v$ of $G_1$ and $u$ of $G_2$. Make those edge's weight to $0$. Now, find a shortest path between $s_1$ and $t_2$ (using Djikstra)

4

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 your own. Dijkstra's algorithm never works when there is a negative weight cycle. If a graph has negative weights, but no negative weight cycles, it is possible ...

4

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 new edge +3W/2. Any path through these two new edges will still have a contribution W from the two edges together . You still need to prove that Dijkstra works ...

3

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 with an even number of red edges found so far, and the shortest with an odd number. Here's a more precise description of the algorithm. For each vertex $v$, ...

3

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 $w(s,t) = 2$. Here the Dijkstra's algorithm with negative weights would give the shortest path $(s,t)$. However, the shortest path is $s$->$u$->$t$, which ...

3

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 denote it as $p_{CB}$. Then we would have a path $A \rightarrow p_{CB} \rightarrow F \rightarrow E$ from $A$ to $E$ which is shorter than $A \rightarrow C \... 3 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 that no optimal solution is ever going to come back to the source again and refill. Similarly, we also assume that the$\text{target}$also has a gas station with ... 2 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 that let you find the shortest path to any vertex of the graph. The idea is to always consider the vertices that you reach from the cheapest (closest) node of the ... 2 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 just follow the shortest one of these to get the next node because the next shortest path might not be to a neighbor of the current node. Thus we enqueue it as ... 2 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 mentioned in the question does not use a shortest path first search. You might have overlooked the following statement in that article We now need to pick a new ... 2 You are right. Checking k < d[u] is not sufficient and updating d[u] on the next line is not necessary. The check prevents proceeding when the source is picked up from the queue (then k = 0 and d[s] = 0). Also, d[u] (u is fixed) is monotonically decreasing as loop proceeds, so even though it is updated after (u, d[u]) is put on the queue, k >= d[u] ... 2 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 1 for each. You can then visit a "clause" for free if and only if one of its literals is selected. Now, the cheapest s-t-path costs$n$if and only ... 2 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 algorithm can’t be “surprised” by finding a path whose cost drops as more edges are added in. It’s a great exercise to prove that this indeed is the case; it’s ... 2 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 ideas. 2 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. 2 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 vertex$i$and$j$such that$i<j$, there is an edge of unit weight if$j = i+1$; and there is an edge of weight$2(n-i)$if$j > i+1$. Run the heap-based ... 2 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 nodes, respectively. When the set of intermediate nodes is$V \setminus \{s,t\}$the problem is equivalent to finding an Hamiltonian path from$s$to$t$in$G$, ... 2 Consider what will happen for the following graph. counterexample_graph = { 'U': {'V': 6, 'W': 7}, 'V': {'X': 10}, 'W': {'X': 1}, } Suppose U is the starting vertex. You can check that vertex X is added to the priority queue by route U -> V -> X, yielding a distance of 16, then by route U -> W -> X, yielding a shorter distance of ... 1 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 walk any number of times we want in that negative cycle - which will just continue to decrease the path's cost. Essentially this means you tried to compare two ... 1 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 the shortest path to our vertex$d$is the path$s \to u_1 \to u_ 2 \to \cdots \to u_l \to x \to \cdots \to d$Where nodes$s, u_1, u_2, \cdots, u_l$are ... 1 This is not the right place to ask for people to review your code, but it's perfectly normal for Dijkstra's algorithm and Uniform Cost Search (BFS) to return different paths. Indeed, a shortest path on a weighted graph is not necessarily the one that uses less edges. As an example you can consider the graph$G=(V,E)$with$V=\{s,u,v\}$,$E=\{(s,u), (u,v), (s,...

1

You can do this in polynomial time with a greedy algorithm by always traveling to the nearest un-visited terminal, and dropping a portal in every terminal. The crucial observations are these: Since it's free to drop a portal and use one, you always put a portal in each of the terminals. There is no point traveling anywhere but to a terminal. When you move ...

1

First of, you can make some of the bounds a little tighter and replace some $E$s with $V$s. The while loop at the beginning will only run $O(|V|)$ iterations (you visit every node only once), and the for (Edge edge : graph.adj(min)) loop will run only $O(|V|)$ iterations at most (a node can have at most $O(|V|)$ adjacent edges). Same with the log factors, ...

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