Leetcode刷题：Dijkstra算法空间复杂度及邻接表空间疑问

1. Visit集合与优先队列的空间复杂度 #

你的理解不完全准确，分两部分拆解：

• visit集合：每个顶点只会被加入一次，空间复杂度确实是O(V)，这部分判断正确。
• 优先队列（maxHeap）：你的代码里虽然判断了nei not in visit才入队，但要注意：一个顶点可能在被标记为已访问前，被多条不同路径的条目推入堆中。比如顶点B可能通过顶点A、C分别生成不同概率的路径，在B被弹出堆并加入visit前，这两个条目都会存在于堆里。最坏情况下，堆的大小会达到O(E)（每条边对应一次入堆操作）。
  整体来看，visit+优先队列的总空间复杂度是O(V+E)，而非单纯的O(V)。

2. 邻接表（Python dict实现）的空间复杂度 #

用dict构建的邻接表，空间复杂度确实是O(E)。每条边会被存储一次（无向图则对应两个顶点的邻接列表，总空间还是O(E)量级），顶点本身的存储是O(V)，通常我们说邻接表的空间复杂度是O(V+E)，但核心边的存储部分符合你判断的O(E)。

补充优化提示 #

如果想压缩优先队列的空间，可以在入队前增加判断：只有当前路径的概率（或对应问题的最优值）比已知的该顶点最优值更好时，才推入堆。这样能避免同一顶点的无效路径重复入队，让堆的空间更接近O(V)。

内容的提问来源于stack exchange，提问作者Sam J