有没有什么高效的算法可以解决约束最短路径问题?

问题描述 投票:0回答:0

假设有一个有向网络,其边具有成本和距离两个属性。现在,需要在满足一定距离限制且具有最小成本的不同起点-终点对之间找到最优路径。距离限制可能因不同的起点-终点对而异。

如果我们使用拉格朗日松弛法、k-最短路径或标签算法,我们只能为每个起点-终点对计算一次最优路径。如果有很多这样的对(例如 10,000 对),这些方法将非常低效。是否可以使用类似于 Dijkstra 算法的单源约束最短路径算法来有效地解决这个问题?

graph-theory shortest-path
© www.soinside.com 2019 - 2024. All rights reserved.