我有一个任务来实现 Dijkstra 算法。我们得到了将图形作为邻接矩阵输入的骨架代码，但告诉我们的解决方案必须在 O(MlogN) {M-edges, N-vertices} 中运行。我看到了 PQ 和列表结构将如何实现这一点，但我看不出在我的情况下如何避免 O(N^2) 解决方案。摆脱矩阵的唯一方法是遍历每一行和每一列......对吗？
问问题
4383 次
1 回答
1
错误的。您的任务不是对矩阵中的每个值执行操作，而是找到 2 个节点之间的最短路径。在您的情况下，矩阵是保存数据的媒介，它不会改变算法的复杂性。该O(MlogN)算法可免费获得，例如：Dijkstra's algorithm。
于 2012-11-26T18:29:03.100 回答