Dijkstra's algorithm with minimum edge

Question

So first let's define Dijkstra algorithm:
Dijkstra's algorithm finds single-source shortest paths in a directed graph with non-negative edge weights.
If I have a source S and destination T I can find a shortest path between this two vertices with Dijkstra algorithm but here is the problem I want to find the shortest path between this two vertices which the number of edges between this two does not exceed form K.
The first part is Dijkstra algorithm but second is kind of BFS algorithm because we can find the shortest path in none weighted graph with BFS algorithm.
So I am wondering is there a way that can some how change the dijkstra in order to solve this problem?
Any solution would be grateful.

for example let's define k=4 we have path between S and T that contain 5 edge and the cost of this path is 10 and this is the shortest path but we another path with 3 edge but the cost is 11 I want to find this path with dijkstra algorithm — Daniel.V
– Daniel.V, Commented Feb 16, 2015 at 19:58
@ user2225104 Sorry I edit my question that second T was K that was my mistake I'am so sorry — Daniel.V
– Daniel.V, Commented Feb 16, 2015 at 19:59

amit · Accepted Answer · 2015-02-16 20:01:26Z

5

You can use Bellman-Ford's algorithm, and instead to run until |V| - 1 in the outer loop, run until k. The outer loop iterator indicates the maximal length of the shortest path from the source to each target.

From wikipedia (with the outer loop index modification)

   for i from 1 to k: //here up to k instead to |V|
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

answered Feb 16, 2015 at 20:01

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

advocateofnone Over a year ago

Was just about to post the same but was not sure it was correct :) +1

Daniel.V Over a year ago

what a brilliant idea how can I missed it thank you so much :)

mrk Over a year ago

You should use a second array to update the distances and then copy them back to the distance array.

Collectives™ on Stack Overflow

Dijkstra's algorithm with minimum edge

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related