25 votes
Accepted

Why can't we find shortest paths with negative weights by just adding a constant so that all weights are positive?

Adding a weight to every edge adds more weight to long paths than short paths. (Long in the sense of having many edges.) For example, suppose the lowest-cost edge has weight $-2$ and there are ...
David Richerby's user avatar
23 votes

What is the meaning of 'breadth' in breadth first search?

Consider the data structure used to represent the search. In a BFS, you use a queue. If you come across an unseen node, you add it to the queue. The “frontier” is the set of all nodes in the search ...
Throckmorton's user avatar
16 votes
Accepted

A* graph search time-complexity

These are basically two different perspectives or two different ways of viewing the running time. Both are valid (neither is incorrect), but $O(b^d)$ is arguably more useful in the settings that ...
D.W.'s user avatar
  • 158k
14 votes

Why does Dijkstra's algorithm fail on a negative weighted graphs?

Adding a constant amount to each edge length can change the shortest path for the simple reason that it increases the length of a path with many edges by more than it increases the length of a path ...
David Richerby's user avatar
13 votes

How does consistency imply that a heuristic is also admissible?

To proof the statement in your question, let us proof that consistency implies admissibility whereas the opposite is not necessarily true. This would make consistency a stronger condition than the ...
Carlos Linares López's user avatar
12 votes

Minimum spanning tree vs Shortest path

I think an example will make it clearer.. The spanning tree looks like below. This is because if we add up the edges in this configuration, we get the least total cost possible: 2+5+14+4=25. ...
Pithikos's user avatar
  • 393
11 votes
Accepted

Shortest path between two points with n hops

If vertices can be visited more than once, then yes: you can create $n+1$ copies of the graph, with each vertex $v$ in the original graph becoming the $n+1$ vertices $v_1, \dots, v_{n+1}$ and each ...
j_random_hacker's user avatar
11 votes
Accepted

Find shortest path between two vertices that uses at most one negative edge

You can use Dijkstra twice to find in your $G'$ the cost for each vertex $v \in V$, the cost of the optimal $s$-$v$-path and the cost of the optimal $v$-$t$-path. Store this in a table creatively ...
Pål GD's user avatar
  • 15.8k
11 votes

Find shortest path between two vertices that uses at most one negative edge

Another approach is to create a single graph $H$ as follows: each vertex in $G$ has two counterparts in $H$: vertex $s$ becomes $s_A$ and $s_B$, vertex $t$ becomes $t_A$ and $t_B$, and so on. each ...
ruakh's user avatar
  • 623
10 votes
Accepted

Finding all edges on any shortest path between two nodes

Off the top of my head, you could do this. (Let's say you want to find all edges on a shortest path from $s$ to $t$.) Run an All-Points Shortest Path (APSP) algorithm to store the shortest-path ...
Draconis's user avatar
  • 7,078
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
  • 38.8k
8 votes

Why can't DFS be used to find shortest paths in unweighted graphs?

You can!!! Mark the nodes as visited while you are going depth and unmark while you return, while returning as you find another branch(es) repeat same. Save cost/path for all possible search where ...
cosmos's user avatar
  • 181
7 votes
Accepted

How to find the shortest path from some vertex in set $S$ to set $S'$

If all edge lengths are non-negative, then this can be solved in $O(|E| \lg |V|)$ time using a single invocation of Dijkstra's algorithm. We're going to modify the graph slightly by adding a new ...
D.W.'s user avatar
  • 158k
7 votes
Accepted

Linear time algorithm for finding $k$ shortest paths from $s$ to $t$

First of all, the answer that applies here was already given by Raphael in the comments to the question: "Given that we don't even know how to find one simple shortest path in linear time, I doubt it."...
Carlos Linares López's user avatar
7 votes
Accepted

Can we find k shortest paths between all pairs faster than solving the pairwise problem repeatedly?

First of all, a crucial difference in computing $k$-shortest paths is if the paths need to be simple or not. A path is called simple, if it does not contain nodes repeatedly. A path with a loop, for ...
FiB's user avatar
  • 86
7 votes

Can I run Dijkstra's algorithm using priority queue?

Yes, you can use priority queues to improve the complexity of the algorithm from $O(V^2)$ to $O(|E| + |V| \log|V|)$ where $E$ is the number of edges and $V$ is the number of nodes. You ...
GT7's user avatar
  • 171
7 votes
Accepted

Shortest walk through a given subset of edges

This is NP-hard, so it's very unlikely that a polynomial-time algorithm exists. Given any instance $G=(V, E)$ of Hamiltonian Path, create a new graph $G'=(V', E')$ in which every vertex $v \in V$ ...
j_random_hacker's user avatar
7 votes
Accepted

Finding shortest paths in undirected graphs with possibly negative edge weights

I contacted one of the authors (Kevin Wayne; thanks) of the textbook "Algorithms, 4th Edition" and got a hint: Try adding "t-joins" or "perfect matching" to your web searches. Following this, I ...
hengxin's user avatar
  • 9,521
7 votes
Accepted

Dijkstra with max instead of sum

Yes, it is true. Let $w: E(G) \to \mathbb{R}$ be a weight function on the edges of $G$, $s \in V(G)$ be the start vertex. Let $p(v) = \min\{\max\{w(e_1), \ldots, w(e_k)\} \mid e_1, \ldots, e_k \text{...
Artur Riazanov's user avatar
7 votes
Accepted

Shortest paths between given red vertices and arbitrary blue vertices

I assume no negative weights in this solution (since you stated Dijkstra). My solution also uses Dijkstra. Let $G'$ be the graph resulting from $G$ by contracting all the blue vertices into one vertex ...
Narek Bojikian's user avatar
6 votes
Accepted

Finding all vertices on negative cycles

If you don't constrain yourself to simple cycles, you can actually use the Bellman-Ford algorithm to find all the relevant vertices. Start by running a DFS on the graph to find its strongly connected ...
Mickey's user avatar
  • 563
6 votes
Accepted

Dijkstra's algorithm on huge graphs

There are libraries available to compute shortest paths on such graphs. How do they do this? More specifically, how do they load the required part of the graph to run Dijkstra's algorithm? You can ...
Karussell's user avatar
  • 176
6 votes

Dijkstra with bitwise OR of edge costs

I'm not sure if you can adapt Dijkstra specifically in any way to this problem, but there's a different efficient solution that's actually easier to come up with. Because bitwise operators treat bits ...
Mihai's user avatar
  • 416
6 votes
Accepted

Where does the heuristic come from in the A-star algorithm and how do we know it has the right properties?

(i) Where do the heuristic values for shortest distance come from? There is mention of "straight roads" but I don't understand this. I know "heuristic" is "informed guess" but why not values 1237, 978,...
David Richerby's user avatar
6 votes

Compute single-source shortest paths in O(n+m) time?

There are many ways to solve this problem in linear time. I'll write the one I found easiest to understand. The main idea is to transform the weighted graph into an unweighted one. If the number of ...
Christopher Boo's user avatar
6 votes
Accepted

How hard is finding the shortest path in a graph matching a given regular language?

This problem can be solved in polynomial time by a product construction. Construct the graph $G^\prime$ as follows: The vertices of $G^\prime$ are $(V \times M) \cup \{\#\}$, i.e. all pairs of a ...
Aaron Rotenberg's user avatar
6 votes
Accepted

Diameter of a disconnected graph

The distance $d_G(u,v)$ between two disconnected vertices $u,v$ of a graph is usually defined as $+\infty$. As a consequence the diameter of a disconnected graph $G=(V,E)$ is $$ \textrm{diam}(G) = \...
Steven's user avatar
  • 29.4k
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
Accepted

Dijkstra's algorithm to compute shortest paths using k edges?

If the graph has no negative edges, the problem can be solved in $O(k \cdot (|V|+|E|) \lg |E|)$ time using Dijkstra's algorithm combined with a product construction. We construct a new graph $G'=(V',...
D.W.'s user avatar
  • 158k
5 votes
Accepted

Is it possible to produce different shortest path trees using bellman ford and Dijkstra algorithm?

If there are multiple shortest paths (equal distances), you could get different results even between two runs of Bellman Ford, if for instance, the two runs consider edges in different orders. But, ...
Algorithms with Attitude's user avatar

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