我正在研究 Dijkstra 的现有实现,我的交付成果之一是测试该实现是否是当前问题的有效解决方案或推荐替代算法。 问题是......我应该如何为现有的 Dijkstra 算法制定基线,以便我可以将其与替代算法进行比较? 为了缩小范围,我的客户正在使用 Dijkstra 为 B2B 消费者动态选择最佳关税计划。这有什么意义吗?
最佳答案
Dijkstra是一种查找图中最短路径的算法。要测试并了解其效果如何,您需要将其与其他算法进行比较。像Bellman–Ford算法,A* search algorithm等
重要说明
除了性能之外,还有其他重要问题,例如 Dijkstra 不适用于负值。这就是为什么在许多问题中都使用贝尔曼-福特法。
此外,Dijkstra 有不同的实现。
带列表的 Dijkstra 算法来自 O(V 2),带修改二进制堆的 Dijkstra 算法来自 O((E + V) log V),带 Fibonacci 堆的 Dijkstra 算法来自 O(E + V log V)。 Bellman–Ford 算法来自 O(VE)。
结论
如果您需要了解哪个参数更适合您的工作,请首先查看哪些参数对您很重要,然后比较适合的参数。如果您愿意,您甚至可以测试它们,因为它们之前都已被其他人实现过。您只需要给他们一个图表
关于algorithm - 如何高效测试 Dijkstra 算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39462285/