# Tag Info

46

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 ...

39

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 ...

37

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 ...

33

Since this is an unweighted graph, you could run a Breadth First Search (BFS) from every vertex $v$ in the graph. Each run of BFS gives you the shortest distances (and paths) from the starting vertex to every other vertex. Time complexity for one BFS is $O(V + E) = O(V)$ since $E = O(V)$ in your sparse graph. Running it $V$ times gives you a $O(V^2)$ time ...

23

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 ...

22

You can implement Dijkstra's algorithm as BFS with a priority queue (though it's not the only implementation). Dijkstra's algorithm relies on the property that the shortest path from $s$ to $t$ is also the shortest path to any of the vertices along the path. This is exactly what BFS does. Or in another perspective: how would Dijkstra's algorithm behave if ...

17

The problem you are asking for is a well-known algorithmic problems. It is actually still open, how hard this problem exactly is. Also you should know that there are different incarnations of this problem. In contrast what you are asking for, usually only the distances are returned, whereas you are asking for the the actual shortest paths. Notice that these ...

16

If edge weights are integers in $\{0,1,\ldots,K\}$, you can implement Dijkstra's to run in $O(K|V|+|E|)$ time, following @rrenaud's suggestion. Here is a more explicit explanation. At any time, the (finite) keys in the priority queue are in some range $\{D,D+1,\ldots,D+K\}$, where $D$ is the value of the last key removed from the priority queue. (Every key ...

15

You are right for the most part. Just one more addition. When you go back the predecessor chain when trying to find the cycle, you stop when you either reach the starting vertex $v_1$ or any other vertex that has already been seen in the predecessor chain that you have seen so far. Basically, you stop and output vertices whenever you detect a cycle when ...

15

Consider the shortest path from $s$ to $t$, $s, v_1, v_2, \dots, v_k, t$. This path consists of at most $|V|-1$ edges, because repeating a vertex in a shortest path is always a bad idea (or at least there is a shortest path which does not repeat vertices), if we do not have negative weight cycles. In round one, we know that the edge $(s, v_1)$ will be ...

14

The problem as you probably have noticed is a quite difficult problem. Checking the web will lead to some complex instances that probably you will not need. Here is a solution - as required (i.e. you dont need to recalculate everything from scratch). for the case of adding an edge $(u,v)$ - then using your already built-distance matrix - do the following : ...

13

The only element of depth-first search you tweak is the order in which children are investigated. The normal version proceeds in arbitrary order, i.e. in the order the children are stored. The only feasible alternative (towards shortest paths) I can come up with is a greedy approach, that is looking at children in order of their distance from the current ...

13

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 ...

12

This is precisely Moore's 1957 formulation of what is now more commonly known as the Bellman-Ford algorithm. Why does it work? Moore's algorithm is a special case of Ford's more general relaxation strategy for computing single-source shortest paths: while any edge is tense relax any tense edge This generic algorithm will always halt after a finite ...

12

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 ...

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

Since you allow non-simple paths(i.e. walks), seems like a dynamic programming algorithm will work. For each $1 \le m \le k$, and every vertex $u$, we compute $D[m,u]$ where $D[m,u]$ is the weight of the shortest walk of length exactly $m$ starting at $v$ and ending at $u$. We are looking for $D[k,w]$. This can be computed as D[m+1, u] = \min_{x \in ...

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

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 ...

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 ...

10

Breadth-first-search is the algorithm that will find shortest paths in an unweighted graph. There is a simple tweak to get from DFS to an algorithm that will find the shortest paths on an unweighted graph. Essentially, you replace the stack used by DFS with a queue. However, the resulting algorithm is no longer called DFS. Instead, you will have implemented ...

10

For the shortest path problem, if we do not care about weights, then breadth first search is a surefire way. Otherwise Dijkstra's algorithm works as long as there are no negative edges. For longest path, you could always do Bellman-Ford on the graph with all edge weights negated. Recall that Bellman-Ford works as long as there are no negative weight cycles,...

10

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$ ...

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

Here is a reduction of CNF-SAT. In a given CNF formula, assume we have variables $x_1, \dots, x_n$ and clauses $C_1, \dots, C_m$. We construct a DAG with edge colors as follows. We have $m$ colors, and each color corresponds to a clause. In our DAG, we have vertices $v_0$, $v_1$, ..., $v_n$, and $v_0$ is the source and $v_n$ is the sink. (There will be ...

8

Let $n = |V(G)|$ and $m = |E(G)|$. Let $w(a \to b)$ denote the weight of the edge $(a \to b)$. Suppose that you want to find the minimum and maximum path cost from $s$ to $t$. Starting from $b := t$, perform the following: If $b$ has already been visited, return the already computed $\min(b)$ and $\max(b)$. Otherwise mark $b$ as visited. Determine and ...

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

There is Johnson's algorithm, whose running time is $O(V^2\log V + VE)$.

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