Dijkstra的算法具有最小边缘

Question

首先让我们定义Dijkstra算法:
Dijkstra算法在具有非负边权重的有向图中找到单源最短路径.
如果我有一个源S和目的地TI可以用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