# Tag Info

54

Consider the triangle graph with unit weights - it has three vertices $x,y,z$, and all three edges $\{x,y\},\{x,z\},\{y,z\}$ have weight $1$. The shortest path between any two vertices is the direct path, but if you put all of them together you get a triangle rather than a tree. Every collection of two edges forms a minimum spanning tree in this graph, yet ...

49

You are right that the two algorithms of Dijkstra (shortest paths from a single start node) and Prim (minimal weight spanning tree starting from a given node) have a very similar structure. They are both greedy (take the best edge from the present point of view) and build a tree spanning the graph. The value they minimize however is different. Dijkstra ...

42

Dijkstra relies on one "simple" fact: if all weights are non-negative, adding an edge can never make a path shorter. That's why picking the shortest candidate edge (local optimality) always ends up being correct (global optimality). If that is not the case, the "frontier" of candidate edges does not send the right signals; a cheap edge might lure you down a ...

25

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 two paths from $a$ to $b$: a single edge of weight $3$ and a path with two edges, each of weight $1$. The two-edge path has the lowest weight. ...

23

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 data structure. The queue will will iterate through all nodes on the frontier sequentially, thus iterating across the breadth of the frontier. DFS will always ...

16

Though Minimum Spanning Tree and Shortest Path algorithms computation looks similar they focus on 2 different requirements. In MST, requirement is to reach each vertex once (create graph tree) and total (collective) cost of reaching each vertex is required to be minimum among all possible combinations. In Shortest Path, requirement is to reach destination ...

13

I can offer an example for super-exponentially many shortest paths and super-polynomially many minimum cuts. An example for many shortest s-t-paths you probably came up with is the layer graph, similar to the one here. Turns out we can use the same idea here -- all we have to do is use many layers so that there are many minimum cuts, and fiddle with the ...

13

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 typically arise in AI. In the algorithms community and CS theory community, folks there tend to like to count the running time as a function of the number of ...

12

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 with only a few edges. For a simple case, consider the graph with vertices $\{a,b,c\}$ and edges $\{ab,bc,ac\}$, where $ab$ and $bc$ have length $1$ ...

12

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 latter. Consistency implies admissibility: Let me start by emphasizing that $h(t)=0$ if the heuristic function $h$ is admissible (where $t$ is a goal) since edge ...

11

It is NP-complete to even decide whether any path exists. It is clearly possible to verify any given path is a valid path in the given graph. Thus the bounded-length problem is in NP, and so is its subset, the any-path problem. Now, to prove NP-hardness of the any-path problem (and thus of the bounded-length problem), let's reduce SAT-CNF to this problem: ...

11

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 edge $uv$ in the original graph becoming the set of edges $u_iv_{i+1}$ for all $1 \le i \le n$; now run Dijkstra on the resulting graph with start vertex $A_1$ and ...

9

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 distances from every node to every other node For every edge $a \rightarrow b$ in the graph: Add up the distance from the $s$ to $a$, and the weight of the edge, ...

8

You can try to make a version of Floyd-Warshall that is faster on sparse matrices. First, let us recall what this algorithm does: Let $M$ be a matrix of distances. At the beginning of the algorithm $M_{i,j}$ is the weight of the edge $i \rightarrow j$. If this edge does not exist then $M_{i,j}=\infty$. The algorithm has $V$ steps. In step $k$ of the ...

8

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 you found the target node, compare all such cost/path and chose the shortest one. The big(and I mean BIG) issue with this approach is that you would be visiting ...

8

Most real mazes are trees and there is a polynomial time algorithm for this problem on trees. For ease of description, orient all edges of the tree to point away from the start vertex. Now, for each vertex, delete any child if the subtree rooted at that child contains no vertices that must be visited (i.e., contains no grey or red vertices). The result is a ...

8

Google Maps in 2009 used Contraction Hierarchies - see this tech talk. Since then, some mind-blowing methods have been discovered, capable of doing cross-country routing in fractional milliseconds - the so-called "two-hop labeling distance oracles". See here, or search for "Hub labeling" or "Shortest paths for the masses". I think I heard Bing uses this one....

7

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. (1) (4) \ / (2) / \ (3) (5) By eyeballing the spanning tree you might falsely think that it gives you the shortest paths, but in practice it doesn't. ...

7

The difference lies in what is the ultimate goal of this algorithms- Dijkstra's - Here the goal is to reach from start to end. You are concerned about only this 2 points, and optimize your path accordingly. Krusal's - Here you can start from any point and have to visit all other points in the graph. So, you may not always choose the shortest path for any ...

7

Take any graph $G$ on $n$ vertices which has $2^{\Omega(n)}$ minimal $s$-$t$ paths. Add to $G$ an independent set of size $n$. Now it has at least $2^n$ minimum cuts.

7

Answering your first question is simple. Try out a few graphs and see for yourself why it doesn't work. As to your second question, $n-1$ is the maximal length of a shortest path in the graph. After $k$ iterations of the Bellman–Ford algorithm, you know the minimum distance between any two vertices, when restricted to paths of length at most $k$. This is why ...

7

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 vertex $s$. Also, add an edge of length 0 from $s$ to each vertex in $S$. Next, run Dijkstra's algorithm, starting from the source vertex $s$. Dijkstra's ...

7

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." In the following, thus, I will assume you are interested in knowing about the best available algorithms in the current state of the art. In the following, I ...

7

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 example, is not simple. Note that on the Wikipedia page you linked, the articles are concerned with not necessarily simple paths. The case of simple paths seems ...

7

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 should consider carefully the number of nodes in your graph and the desired run time before adding complexity to your implementation. See here for a brief ...

7

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$ becomes a pair of vertices $v_+, v_-$ connected by an edge in $G'$. All of these edges should also be added to $F$. Then for each $(u, v) \in E$, add the ...

7

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 found the following two lecture notes: Shortest Path Algorithms Luis Goddyn, Math 408: Using Edmonds' Minimum Weight Perfect Matching Algorithm to solve shortest ...

7

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 - which means, remove all blue vertices in the graph and add one blue vertex $b$, and for each edge between a red vertex $u$ and a blue vertex $v$, add an edge ...

6

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 components. Let them be $G_1,G_2,...G_k$. For each $G_i$, run BF on the subgraph. If the BF algorithms detects a negative cycle (which it can after $|V_i|+1$ ...

6

I am not 100% sure this answer is correct, but here goes: I think you can reduce this to uniformly random any-paths, from $s-t$, in a DAG with a single source and a single sink. Given a graph $G$ Make a new empty digraph, $H$. First: run the BFS part of Dijkstra's shortest-path, starting from $s$, mark all the nodes with their shortest-distance-from-$s$. ...

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