3
$\begingroup$

I am aware of using Bellman-Ford on a graph $G=(V,E)$ with no negative cycles to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using at most $k$ edges. Assuming we have no negative edge weights at all, can we use Dijkstra's algorithm for the same?

My thoughts/algorithm: I was wondering if instead of having a $dist[u$] array (storing the best known distance from s to u), we could use a $dist[u][k]$ table to store the best known distance from $s$ to $u$ using at most $k$ edges (dynamic programming maybe?), and similarly have the priority queue with $(u,n)$ tuples as keys. We can then terminate the algorithm when the tuple popped off the priority queue is $(t,n)$ where t is the target destination and $n <= k$?

$\endgroup$
  • 1
    $\begingroup$ As far as I remember you can use Dijkstra's algorithm instead of Bellman-Ford when you don't have edges with negative distance in you graph; I'd have to take a closer look at both the algorithms to elaborate more though $\endgroup$ – mewa Feb 16 '16 at 13:04
  • 1
    $\begingroup$ 1. Does the graph have any edges with negative length? 2. What time complexity are you looking for? What's the fastest algorithm you were able to come up with? There's a standard solution based on "the product construction" that increases the running time by a factor of $k$; is that of interest to you? $\endgroup$ – D.W. Feb 17 '16 at 3:20
  • $\begingroup$ See also cs.stackexchange.com/a/43099/755 for a loosely related but not identical problem. $\endgroup$ – D.W. Feb 17 '16 at 3:24
  • 1
    $\begingroup$ I edited to remove a potential confusing point for readers: Bellman-Ford only requires that the graph have no negative cycles; you want to assume more. $\endgroup$ – Raphael Feb 17 '16 at 7:20
  • 1
    $\begingroup$ Note that your target running time, assuming the bound is tight, is worse than Bellman-Ford, which runs in time $O(|V| + k \cdot |E|)$ here. $\endgroup$ – Raphael Feb 17 '16 at 7:25
4
$\begingroup$

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',E')$ with vertex set $V' = V \times \{0,1,2,\dots,k\}$ and edge set

$$E' = \{((v,i), (w,i+1)) : (v, w) \in E\}.$$

In other words, for each edge $v \to w$ in $G$, we have edge $(v,i) \to (w,i+1)$ for all $i$ in $G'$.

Now use Dijkstra's algorithm to find the shortest path in $G'$ from $(s,0)$ to a vertex of the form $(t,i)$ where $i \le k$. This will be the shortest path in $G$ that uses at most $k$ edges.

$\endgroup$
  • $\begingroup$ Since this is slower than Bellman-Ford (in theory, and probably also in practice because we have to construct a new, rather large graph first), I don't see much point -- but the OP asked for it. $\endgroup$ – Raphael Feb 17 '16 at 7:25
  • $\begingroup$ @Raphael, yeah, it does seem a bit pointless to me too. $\endgroup$ – D.W. Feb 17 '16 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.