首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >寻找最佳路径变形强连通构件

问寻找最佳路径变形强连通构件
EN

Stack Overflow用户
提问于 2013-10-26 19:00:43
回答 1查看 1.1K关注 0票数 1

我有一个强连通的有向图,每个节点都有一些代价(正负)。我想找到从节点A到节点B的最佳(最高分数)路径,我的解决方案是某种残酷的力量,所以需要很长时间才能找到这条路径。是否有任何算法来解决这个问题,或者知道我该如何做呢?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2013-10-26 19:06:41

你试过算法吗

这是一种相当流行的路径查找算法。该算法本身并不难实现,但是有大量的在线实现。

Dijkstra算法是A* (其中启发式函数h(x) = 0)的特例。

有其他算法可以超越它,但它们通常需要图形预处理。如果问题不是太复杂,而且你正在寻找一个快速的解决方案,那就试一试。

编辑:

对于包含负边的图,有行李员-福特算法。但是,检测负周期是以性能为代价的(比A*更糟糕)。但它仍可能比你目前使用的更好。

编辑2:

User @templatetypedef说Bellman算法在这里可能不起作用,这是对的。

B适用于有负权边的图.然而,该算法在寻找负循环时停止。我相信这是一种有用的行为。优化包含负权重循环的图中的最短路径,就像沿着Penrose楼梯向下走一样。

如果有可能以“负无穷大成本”到达一条路径,会发生什么情况取决于问题。

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

https://stackoverflow.com/questions/19610682

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档