基于两个度量(距离，成本)的图中的最优(折衷)路径

Question

正如你从我的统计数据中看到的，我在这个论坛上还是个新手，尽管我已经使用stackoverflow.com作为我的编程问题的答案来源有好几年了。我祈祷你能忽略我可能犯下的任何小错误，并分享你对我下面的小问题的想法。

我想知道是否有一种路由/路径查找算法，能够找到随时间推移的最佳路径和可能路由的成本。理想情况下，我可以指定时间、成本或以最佳成本获得最佳时间的偏好。

我一直在使用Dijksta算法在有向加权矩形网络上路由最短路径。所有节点都通过方向边连接到其左、右、上、下以及45°邻居。这意味着所有节点都有8条边，减去外部边界上不存在的边。所有节点都是可到达的，但可以增加度量(距离)以反映更高的成本。我可以在相同的节点上用不同的边列表运行路径查找器，表示遍历它们时的成本(或距离)方面，从而找到最低成本或最快的路径。它为我提供了具有距离度量的最短路线(对于拐角边缘，为1或SQRT(2) )。

现在，我一直在想一种方法，通过简单地将距离和成本方面相乘，从而生成混合度量。你怎么看待这种方法，或者说是一种让路由算法选择不同的“最佳”邻居来找到最佳路由的方法，无论是时间、成本还是折衷。

谢谢。

Answer 1

你可以在新代数中使用任何已知的算法(Dijkstra，Floyd-Warshall)。

把你的距离想象成一个有两个字段的结构：

struct Distance {
    int cost, distance;
}

现在您需要定义operator<和operator+。如果你想以最佳的成本获得最好的时间，你应该使用：

bool operator<(Distance d1, Distance d2) {   
   if (d1.cost == d2.cost) 
       return d1.time1 < d2.time
   else 
       return d1.cost < d2.cost; 
}

或一些权重：

bool operator<(Distance d1, Distance d2) {   
   return wCost*d1.cost + wDistance*d1.distance < wCost*d2.cost + wDistance*d2.distance
}