algorithm - 改进的 Dijkstra 算法

Question

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

我的思路是取边权重的对数值(取模值)，然后对这个图应用 dijkstra，但认为会有无法计算的精度问题。

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

Answer 1

在 Dijkstra 算法中，当您访问一个节点时，您知道没有到该节点的更短路径。如果您将边与 0..1 之间的权重相乘，则情况并非如此，因为如果您访问更多顶点，您将获得较小的数字。

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

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

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

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

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