我有一个强连通的有向图,每个节点都有一些代价(正负)。我想找到从节点A到节点B的最佳(最高分数)路径,我的解决方案是某种残酷的力量,所以需要很长时间才能找到这条路径。是否有任何算法来解决这个问题,或者知道我该如何做呢?
发布于 2013-10-26 19:06:41
你试过算法吗
这是一种相当流行的路径查找算法。该算法本身并不难实现,但是有大量的在线实现。
Dijkstra算法是A* (其中启发式函数h(x) = 0)的特例。
有其他算法可以超越它,但它们通常需要图形预处理。如果问题不是太复杂,而且你正在寻找一个快速的解决方案,那就试一试。
编辑:
对于包含负边的图,有行李员-福特算法。但是,检测负周期是以性能为代价的(比A*更糟糕)。但它仍可能比你目前使用的更好。
编辑2:
User @templatetypedef说Bellman算法在这里可能不起作用,这是对的。
B适用于有负权边的图.然而,该算法在寻找负循环时停止。我相信这是一种有用的行为。优化包含负权重循环的图中的最短路径,就像沿着Penrose楼梯向下走一样。
如果有可能以“负无穷大成本”到达一条路径,会发生什么情况取决于问题。
https://stackoverflow.com/questions/19610682
复制相似问题