改进的Dijkstra算法

Question

我们给出了一个有向图，其边缘权重W介于0和1之间。从源到目标节点的路径成本是位于从源到目标节点的路径上的边的权重的乘积。我想知道一个算法，它可以找到多项式时间的最小代价路径或使用任何其他启发式。

我认为沿着边缘权值（取mod值）的对数值，然后对这个图应用dijkstra，但认为会出现无法计算的精度问题。

有没有其他更好的方法，或者我可以改进日志方法。

Answer 1

在Dijkstra算法中，当你访问一个节点时，你知道这个节点没有更短的路。如果你用0..1之间的权重乘以边，就好像你访问更多的顶点，你会得到更小的数。

基本上这相当于找到图中最长的路径。这也可以通过使用取对数的想法来看到，因为0和1之间的数字的对数是负数。如果您取权重对数的绝对值，则最长路径对应于乘法图中的最短路径。

如果您的图是非循环的，则有一个简单的算法（从Longest path problem修改）。

1. 查找DAG的拓扑排序。
2. 对于每个顶点，您需要存储路径的开销。初始化为一个。
3. 从开始顶点开始按照拓扑顺序遍历DAG。在每个顶点检查所有的孩子，如果成本比以前小，更新它。以最低的成本存储您到达此顶点的顶点。

在到达最终顶点后，您可以使用存储的顶点从末端顶点返回，找到“最短”路径。

当然，如果图形不是非循环的，您可以通过无限重复循环来始终达到零终端成本。