Dijkstra的算法具有最小边缘-Java 学习之路

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

1 回答

5
您可以使用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
```
回复于 2024-04-25T17:19:11+08:00

Dijkstra的算法具有最小边缘

1 回答

相关问题