Dijkstra's algorithm with minimum edge

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 TI 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.

---

You can use Bellman-Ford's algorithm, and instead to run until |V| - 1 |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

链接地址: http://www.djcxy.com/p/35244.html

上一篇: Dijkstra的算法和负权重和周期

下一篇: 具有最小边缘的Dijkstra算法