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
@ user2225104 Sorry I edit my question that second T was K that was my mistake I'am so sorry — Daniel.V

amit amit · Accepted Answer · 2015-02-16T20:01:26

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

Dijkstra's algorithm with minimum edge

1 Answers