具有最小边的 Dijkstra 算法

Question

所以首先让我们定义Dijkstra算法：
Dijkstra 算法在具有非负边权重的有向图中找到单源最短路径。
如果我有源 S 和目标 T 我可以用 Dijkstra 算法找到这两个顶点之间的最短路径但问题是我想找到这两个顶点之间的最短路径这两者之间的边数不超过形式 K.
第一部分是 Dijkstra 算法，但第二部分是一种 BFS 算法，因为我们可以在 none 加权图中用 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

具有最小边的 Dijkstra 算法

Dijkstra's algorithm with minimum edge

algorithm

graph

dijkstra

breadth-first-search