关于Dijkstra

回复帖子

@Immortalbelie 2021-09-15 13:29 回复

朴素Dijkstra的时间复杂度为 $ O(n^{2}) $ ,而用了堆优化的话是 $ (n+m)log_2 n $ 。那是否当 $ m $ 足够大的话,反而是朴素算法快一些

@ftiasch 2021-09-15 15:02 回复 举报

但是你可以用 Fibonancci Heap,这样复杂度是 $O(n \log n + m)$! 无论是稀疏图还是稠密图都一样快!

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。