Dijstra最短路径算法，priorityqueue是必须的吗？

wl0211 · 2018-12-30 09:19:29

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

请教各位大佬，今天刷图的题遇到的问题。我一开始用queue放的节点但是有testcase过不了。后来发现大家都用的pq，讨论区也有人说不用的。我Google了一下也只找到说pq可以优化，请大佬指点，谢谢

PandaLeaves · 2018-12-30 13:20:53

如果你每次直接pop队列顶端，那么你得到的应该是一个类似SPFA的算法吧...

stultus · 2018-12-30 10:59:57

pq可以降时间复杂度…你寻最小遍历一边是O（n），往pq里不断的插所有距离然后寻最短时间复杂度是O（log（n））（因为pq是最小堆结构。

xiebw · 2018-12-30 12:42:16

算法导论上应该有吧，隐约记得binomial heap是最优秀的

Airtnp · 2018-12-30 13:17:57

优化Extract-Min+Insert或者Decrease Key
所以还有Fibonacci堆的优化

PocketOffer · 2018-12-30 15:20:52

你如果每条边的权重不一样的话用QUEUE怎么求极值呢？

wl0211 · 2018-12-30 20:03:02

感谢大家，又看了一遍算法导论，弄清楚了，谢谢大家~

[树/链表/图] Dijstra最短路径算法，priorityqueue是必须的吗？