最小边Dijkstra算法

Question

首先定义Dijkstra算法:
Dijkstra的算法在有向图中寻找具有非负边权的单源最短路径。
如果我有源和目的地T，我可以用Dijkstra算法在这两个顶点之间找到一条最短路径，但这里的问题是我想找到这两个顶点之间的最短路径，这两个顶点之间的边数不超过形式k。
第一部分是Dijkstra算法，第二部分是BFS算法，因为我们可以用BFS算法在无权图中找到最短路径。
所以我想知道有没有一种方法，可以改变dijkstra以解决这个问题？
任何解决方案将是感激的。

Answer 1

您可以使用Bellman-Ford的算法，而不是在外循环中运行直到v-1为止，而是运行直到k为止。外循环迭代器指示从源到每个目标的最短路径的最大长度。

来自维基百科（带有外圈索引修改）

   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