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

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

• 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
– mewa
Feb 16 '16 at 13:04
• 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?
– D.W.
Feb 17 '16 at 3:20
• See also cs.stackexchange.com/a/43099/755 for a loosely related but not identical problem.
– D.W.
Feb 17 '16 at 3:24
• 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.
– Raphael
Feb 17 '16 at 7:20
• 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.
– Raphael
Feb 17 '16 at 7:25

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.

• 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.
– Raphael
Feb 17 '16 at 7:25
• @Raphael, yeah, it does seem a bit pointless to me too.
– D.W.
Feb 17 '16 at 8:10