文章/答案/技术大牛

发布

社区首页 >问答首页 >带最小边的Dijkstra算法

问带最小边的Dijkstra算法
EN

Stack Overflow用户

提问于 2015-02-16 19:50:38

回答 1查看 1.5K关注 0票数 4

首先，让我们定义迪克斯特拉算法：

Dijkstra算法在具有非负边权的有向图中寻找单源最短路径.

如果我有一个源S和目标T，我可以用Dijkstra算法在这两个顶点之间找到最短路径，但是我想要找到这两个顶点之间的最短路径，这两个顶点之间的边数不超过形式K。

第一部分是Dijkstra算法，第二部分是BFS算法，因为我们可以用BFS算法在无加权图中找到最短路径。

所以我想知道有什么方法可以改变dijkstra来解决这个问题吗？

任何解决办法都将不胜感激。

graph

dijkstra

breadth-first-search

algorithm

回答 1

Stack Overflow用户

回答已采纳

发布于 2015-02-16 20:01:26

您可以使用贝尔曼-福特算法，在外部循环中运行到|V| - 1，运行到k。外循环迭代器指示从源到每个目标的最短路径的最大长度。

来自wikipedia (外部循环索引修改)

   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

票数 5

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/28549262

复制

相似问题

问带最小边的Dijkstra算法
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问带最小边的Dijkstra算法EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问带最小边的Dijkstra算法
EN