algorithm - 具有最小边的 Dijkstra 算法

Question

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

Answer 1

您可以使用 Bellman-Ford's algorithm ，而是一直运行到 |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