具有最小边缘的Dijkstra算法
首先让我们定义Dijkstra算法：
Dijkstra算法在具有非负边权重的有向图中找到单源最短路径。
如果我有一个源S和目标TI可以通过Dijkstra算法找到这两个顶点之间的最短路径，但这里是我想要找到这两个顶点之间的最短路径的问题，这两个顶点之间的边数不超过K 。
第一部分是Dijkstra算法，第二部分是BFS算法，因为我们可以用BFS算法找到没有加权图的最短路径。
所以我想知道是否有一种方法可以改变dijkstra以解决这个问题？
任何解决方案将不胜感激。
您可以使用Bellman-Ford的算法，而是运行到|V| - 1 |V| - 1在外循环中|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