Skip to main content
Tweeted twitter.com/StackCompSci/status/700517045566365696
edited tags
Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

I am aware of using Bellman-Ford on a graph $G=(V,E)$ with positive edge weightsno negative cycles to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using atmostat most $k$ edges. CanAssuming 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$?

I am aware of using Bellman-Ford on a graph $G=(V,E)$ with positive edge weights to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using atmost $k$ edges. 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$?

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

added 33 characters in body
Source Link
Mathguy
  • 411
  • 5
  • 14

I am aware of using Bellman-Ford on a graph $G=(V,E)$ with positive edge weights to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using atmost $k$ edges. Can we use Dijkstra's algorithm for the same?

My thoughts yet/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$?

I am aware of using Bellman-Ford on a graph $G=(V,E)$ to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using atmost $k$ edges. Can we use Dijkstra's algorithm for the same?

My thoughts yet: 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$?

I am aware of using Bellman-Ford on a graph $G=(V,E)$ with positive edge weights to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using atmost $k$ edges. 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$?

Source Link
Mathguy
  • 411
  • 5
  • 14

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

I am aware of using Bellman-Ford on a graph $G=(V,E)$ to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using atmost $k$ edges. Can we use Dijkstra's algorithm for the same?

My thoughts yet: 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$?