# Tag Info

## Hot answers tagged shortest-path

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

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

### 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 ...
• 3,463

### 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. ...
• 393
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 ...
• 5,479
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 ...
• 16.7k

### 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 ...
• 633
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 ...
• 7,148
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 ...
• 39.1k

### 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 ...
• 181
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."...
• 3,463
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 ...
• 86

### 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 ...
• 171
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$ ...
• 5,479
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 ...
• 9,561